A = [
3856534 4039937 23638248 1958360 1962067 1808014 1566593 1575380 1515945 1585997 1811953 2119136 2465310 2747014 3034715 3245257 3199057 3172036 3191115 3042051 3010920 3097176 3062256 3025137 3052807 3527873 3588941 3538951 3913094 3348347 3327999 3234533 2589518 2589309 2579602 2569717 2548134 2496113 2511345 2529836 2528261 2511653 2522943 2521204 2487893 2461982 2451500 2472594 2417378 2445391 2462926 2417220 2466371 2460678 2426333 2408957 2391490 2387972 2333591 2275531 2303296 2284576 2268218 2251210 2232268 2227702 2179368 2260809 2308470 2299654 2434478 2518555 2537098 2559856 2585399 2574081 2560372 2552339 2519282 2494432 2469356 2453896 2435547 2413161 2407092 2365526 2319429 2256071 2204059 2190717 2166496 2150331 2142907 2128875 2109230 2098765 2072322 2055662 2026452 1999662 1987475 1972258 1951843 1952321 1940846 1921423 1910275 1884429 1864731 1846204 1824851 1810840 1799816 1790784 1778259 1771280 1758086 1740058 1721212 1700358 1685765 1667341 1653972 1638694 1633207 1621162 1608387 1591607 1569739 1547348 1534971 1514753 1497863 1491431 1483972 1473724 1462127 1449837 1427959 1412573 1397314 1378527 1365293 1353720 1340371 1330100 1321805 1308159 1291436 1278871 1260645 1243990 1232629 1217890 1206185 1191926 1185070 1170144 1158811 1145556 1134383 1115154 1101360 1088933 1079307 1065572 1058268 1046803 1035755 1024462 1010234 997117 984564 971722 962496 953198 942153 935862 925275 912557 900698 888694 879332 865315 853953 845374 836387 826206 817825 810111 800888 790115 780570 768774 758014 748185 740838 733054 725739 716580 708599 698749 687692 678839 668873 659778 654141 644716 638766 630850 620865 612903 603946 594687 587156 580316 572869 565618 555808 550525 542341 532626 525482 516705 507185 499524 491206 482706 477050 469865 464640 456693 449862 441607 433953 426476 419850 414138 408338 401704 396427 389863 384519 376753 371168 364849 359357 355443 349191 343268 339069 334561 328533 322144 317563 312338 306634 302517 296770 293792 288296 284234 279695 275350 270011 265089 261823 256395 252471 248506 244939 240910 237561 233786 229756 225004 221270 217303 214357 210445 207073 204343 200733 197289 194248 191173 187201 184138 180455 177844 175410 172186 169216 166920 163827 160394 158008 155340 152477 149983 146881 144712 142066 139284 137478 135260 133133 130349 128406 126441 123603 121526 119566 117384 115684 113395 111701 109432 107455 105609 103491 101528 100184 97891 95970 94646 92922 91199 89446 88028 86428 84709 83412 81923 80215 79581 77494 76155 74711 73022 71829 70814 69079 68214 66580 66176 65009 63303 62144 61148 59825 58986 58248 57164 55723 55038 53795 53133 52139 51113 50304 49658 48077 47337 46560 45336 44939 44491 43085 42685 42054 41124 39968 39555 38922 38212 37345 36808 36003 35617 34916 34111 33702 32971 32633 31563 31533 30597 30196 29491 29057 28342 27773 27545 27176 26551 26131 25652 25040 24780 23960 23902 23246 23100 22437 21954 21828 21175 20862 20218 20186 19885 19417 18928 18824 18442 17949 17760 17213 17163 16566 16625 16145 16156 15574 15430 15192 14974 14643 14248 14062 13998 13695 13333 12963 12766 12777 12669 12317 11905 11585 11588 11318 11186 11347 10845 10640 10348 10545 10064 9913 9833 9638 9448 9304 9238 8960 8859 8682 8322 8422 8149 8265 7972 7867 7814 7660 7528 7252 7289 7262 7192 6889 6755 6717 6576 6467 6266 6305 6108 6043 5870 5784 5860 5718 5610 5533 5381 5280 5227 5120 5191 5140 4933 4816 4797 4712 4643 4510 4442 4441 4325 4354 4178 4190 4110 4034 3896 4025 3930 3749 3773 3815 3555 3624 3567 3598 3352 3429 3351 3223 3260 3221 3078 3005 3101 3062 2954 2953 2906 2859 2799 2728 2730 2644 2637 2583 2566 2594 2548 2504 2402 2474 2394 2461 2688 2378 2361 2266 2236 2188 2094 2219 2227 2077 1996 1996 2073 2069 1951 1905 1939 1964 1947 1947 1869 1854 1837 1801 1821 1772 1779 1789 1749 1622 1750 1727 1659 1648 1652 1602 1698 1601 1570 1454 1594 1554 1535 1516 1456 1490 1430 1407 1408 1443 1322 1340 1358 1331 1325 1271 1320 1326 1289 1247 1236 1238 1254 1216 1298 1268 1154 1147 1198 1118 1114 1236 1136 1068 1051 1062 1069 1067 960 1052 990 978 1024 932 948 983 967 1012 955 916 956 1000 990 975 933 963 926 868 889 887 876 885 898 843 841 805 805 849 850 799 845 774 792 756 785 800 740 755 740 748 734 731 695 736 725 730 718 689 742 693 721 715 731 737 696 705 678 706 657 647 678 664 668 656 650 632 674 671 655 622 626 604 636 574 605 584 566 613 586 582 587 604 574 600 558 574 532 585 545 553 598 537 542 559 542 550 543 529 503 510 516 524 562 522 539 498 498 512 524 594 551 523 542 511 500 476 507 489 537 533 491 480 483 483 447 465 479 447 476 468 483 467 471 456 452 426 471 458 417 411 421 418 481 467 397 411 427 441 476 438 413 406 433 410 390 415 402 430 405 366 392 351 405 350 431 385 362 348 356 370 350 344 374 337 376 387 357 379 352 333 349 366 367 358 379 356 353 363 376 319 343 345 308 343 313 345 338 314 312 335 307 330 324 316 305 302 326 283 299 304 329 294 316 285 295 330 271 309 301 283 291 302 282 282 291 307 302 262 276 282 318 302 264 303 266 283 281 293 261 259 262 265 262 302 272 292 258 268 259 275 267 272 280 233 231 212 236 254 237 231 256 246 265 228 235 253 238 244 260 224 236 232 240 228 218 204 232 200 217 228 239 218 244 210 191 239 227 233 240 206 208 241 244 204 248 236 190 203 205 209 204 248 217 197 204 235 194 200 215 235 214 191 208 212 217 174 217 196 182 198 183 190 186 192 192 209 186 186 165 191 165 285 169 177 174 165 166 166 205 178 177 148 169 180 176 162 181 185 196 185 176 167 161 150 171 153 167 167 168 166 152 164 140 162 175 194 170 148 164 156 148 175 167 157 167 167 162 166 158 132 165 146 118 148 134 131 149 141 163 154 134 176 134 207 222 161 164 136 172 220 155 359 420 455 262 266 299 383 418 199 429 389 352 403 229 184 163 152 155 130 143 122 124 145 149 138 139 143 141 156 133 117 197 129 144 153 127 121 107 125 102 113 135 106 113 110 110 127 105 124 122 106 145 119 110 117 87 114 116 124 103 96 134 88 112 118 116 117 93 114 136 103 123 113 107 125 119 110 116 137 110 131 121 119 121 116 129 117 142 109 118 145 98 103 130 96 95 102 99 115 115 103 132 137 138 141 141 128 144 149 142 141 135 146 139 128 133 129 119 127 102 139 113 89 91 94 111 104 80 85 103 76 430 96 104 113 115 112 116 85 80 118 91 98 80 85 117 148 97 90 109 85 91 104 77 78 100 81 95 92 90 83 86 87 88 64 85 84 81 92 86 75 77 75 99 68 84 95 87 106 92 86 98 74 105 88 95 115 86 85 99 96 92 106 86 97 92 92 81 75 82 100 74 76 65 71 93 109 78 99 77 80 78 63 69 125 68 82 72 74 113 63 75 83 86 106 87 72 73 88 110 80 75 76 86 101 98 78 85 117 100 101 105 92 108 161 146 135 125 117 138 145 91 96 95 149 118 116 106 155 106 133 120 100 99 120 108 104 76 88 134 108 87 90 76 133 72 74 71 72 110 90 88 74 109 127 80 79 86 87 123 116 91 66 85 190 89 99 66 65 149 73 71 52 74 166 68 52 49 52 59 57 51 55 47 57 37 45 50 72 43 59 45 53 37 56 43 45 65 63 52 44 30 51 41 54 42 47 43 56 37 29 47 45 46 49 40 57 43 49 46 54 45 49 34 49 49 38 34 46 44 39 41 35 46 37 34 48 44 43 51 32 48 41 43 46 41 47 35 45 40 40 50 37 39 32 30 35 33 43 30 37 49 40 45 31 44 65 50 48 52 52 46 49 63 43 42 44 45 41 38 38 29 38 51 39 31 43 31 46 44 35 32 34 46 40 33 38 42 39 40 31 33 37 39 37 20 33 28 34 45 24 27 35 31 41 36 37 41 53 35 39 39 32 56 36 33 27 43 39 38 36 35 32 37 42 41 43 35 33 35 43 34 26 48 35 28 29 32 48 27 33 24 27 32 27 25 32 28 23 41 25 29 40 39 33 42 27 39 40 44 71 63 51 67 50 56 66 84 57 27 51 48 66 58 42 50 59 38 65 47 46 57 58 49 34 61 51 42 61 32 57 56 70 38 40 66 55 40 51 29 56 62 50 59 45 47 45 85 44 42 44 47 39 60 30 40 48 44 33 37 48 60 50 57 43 71 60 55 53 42 54 43 43 42 32 38 45 68 75 53 54 59 50 48 74 33 55 41 46 43 34 41 40 36 24 33 38 34 44 39 22 37 30 31 27 36 37 29 10 22 23 25 16 29 21 29 22 22 22 25 22 14 18 15 17 15 11 29 16 28 32 28 19 19 33 30 33 28 19 29 32 29 22 25 28 28 27 26 21 29 34 25 19 21 29 27 23 13 31 26 30 12 19 22 22 21 23 15 24 36 34 29 30 25 28 25 26 31 15 31 24 32 16 22 21 23 18 12 23 14 14 14 14 14 15 15 23 19 17 17 10 16 18 24 5 21 15 8 16 8 11 11 9 13 20 3 9 15 14 11 9 5 9 11 12 6 10 22 12 15 11 16 12 4 11 11 16 10 14 12 15 9 6 11 12 17 12 11 11 7 21 12 14 9 14 14 13 13 18 18 10 7 15 12 11 9 10 9 19 13 11 16 20 16 15 8 13 17 16 12 12 13 7 16 12 10 14 12 9 16 16 8 12 11 12 12 24 15 14 20 6 12 9 12 8 8 14 9 12 12 11 17 14 13 6 15 14 9 9 18 10 14 9 15 10 7 14 11 9 7 13 7 11 10 10 14 7 12 6 15 7 6 8 9 9 12 10 13 15 10 9 9 10 7 14 11 9 10 13 9 9 11 12 14 11 10 6 17 16 16 21 16 14 9 13 11 15 25 16 6 19 7 13 15 15 15 14 6 13 18 16 12 7 8 11 6 16 10 14 10 13 14 12 14 11 13 14 10 14 9 17 8 9 11 12 7 9 11 9 16 9 9 14 13 11 11 3 8 14 12 13 8 5 6 10 11 15 5 8 8 14 11 11 10 5 6 6 9 15 7 14 10 11 14 7 12 12 6 6 5 8 15 10 7 10 13 7 11 16 16 15 12 11 18 
];
B = [
0 0 0
 1123440 756668 366772
 1374724 956502 418222
 1009447 712313 297134
 2459909 1785144 674765
 1317653 986722 330931
 1004290 763306 240984
 1050534 801677 248857
 803419 620112 183307
 632040 496611 135429
 544983 424372 120611
 688593 534499 154094
 689573 534615 154958
 578888 452184 126704
 2115357 1649391 465966
 941517 748621 192896
 1101793 887130 214663
 931736 761062 170674
 1119041 898795 220246
 1169341 940838 228503
 938996 760397 178599
 1956306 1563769 392537
 1301565 1052908 248657
 1323691 1074668 249023
 981576 804991 176585
 1336806 1091857 244949
 1259639 1027953 231686
 1806256 1465788 340468
 1011406 825029 186377
 1382848 1127352 255496
 1404694 1149813 254881
 1058957 876135 182822
 1463260 1200962 262298
 1339908 1092530 247378
 1826416 1498875 327541
 1075559 891800 183759
 1437533 1179063 258470
 2612902 2174304 438598
 1366146 1124867 241279
 1259134 1049510 209624
 2330951 1941250 389701
 1665529 1370948 294581
 2185233 1818717 366516
 1027591 855629 171962
 1559746 1293549 266197
 2209235 1841617 367618
 1213326 1015414 197912
 2150243 1792838 357405
 1542566 1275385 267181
 2088608 1740435 348173
 1160031 971487 188544
 2039611 1699717 339894
 1571191 1300030 271161
 2051672 1707673 343999
 1086271 914863 171408
 2168927 1808566 360361
 1892903 1577390 315513
 1013270 848969 164301
 1928220 1602714 325506
 1191633 980856 210777
 152160269 130503640 21656629
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 
];
D = [
68 741 2 1
13 81 0 1
35 190 2 1
49 189 4 3
42 162 0 8
87 141 15 17
2210 184 47 62
41493 260 118 121
415253 303 167 194
1314939 345 316 365
1981065 479 4922 1312
2941701 731 7692 2685
4018207 1074 9033 4126
5395329 1993 11223 6292
7089783 3923 13945 9814
8876612 7326 18182 15070
9016269 12102 27099 25178
6796551 19090 41890 40891
3516000 30463 63374 63512
1261594 46044 89464 90328
389597 66144 118306 118490
198027 95460 145874 147843
186319 135765 176935 177547
211053 182011 209956 210784
246497 234176 247755 249252
288475 287191 289886 291740
333660 339893 336494 336966
382068 392498 385990 387414
435277 444285 436834 440342
486829 497765 491889 493973
540943 548046 541231 546011
585623 595223 587959 590364
630098 637441 630142 634765
666699 674285 667082 671085
692515 703783 694369 699575
713566 722935 715292 720734
730907 738710 732972 736507
744660 752083 746957 749339
756101 765095 759019 762775
772121 776010 771137 777208
786946 793193 786065 789889
806482 810194 805434 810717
833730 837559 830849 836101
863154 865541 862867 865474
899074 900158 896146 901450
935873 939342 935187 938423
974683 977114 972099 977577
1006227 1008318 1004276 1011183
1033529 1034286 1031440 1036063
1045478 1048899 1046232 1051237
1041722 1045618 1041504 1048303
1021788 1025447 1021375 1025433
982607 988189 982813 988083
933215 941627 933623 938713
870053 875890 869828 874283
796061 802889 798545 800532
723859 729601 727371 730343
654255 659436 656845 659222
591503 594965 592886 595373
539461 541889 538740 541917
501494 504990 501311 504319
475157 477634 476691 479319
454027 456015 454078 457057
452064 452042 449789 453672
464964 463027 461481 466804
486951 487575 484445 487835
519492 519063 517936 520762
570690 575547 570402 571636
611763 610761 609371 613177
639200 640928 636219 641520
646096 645685 643360 647471
634760 632053 630445 634615
577692 578530 578745 581488
487677 487696 485793 487209
394717 394352 394252 396275
309684 309122 308429 310117
229317 228781 228573 230358
161421 162370 160929 162661
122966 123607 122721 123270
88987 88834 89160 89222
61084 61287 60624 60892
38240 38302 38096 38322
3494 3486 3409 3416
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

];x = [
10 12 15 19 23 28 35 43 53 66 81 100 123 152 187 231 285 351 433 534 658 811 1000 1233 1520 1874 2310 2848 3511 4329 5337 6579 8111 10000 12328 15199 18738 23101 28480 35112 43288 53367 65793 81113 100000 123285 151991 187382 231013 284804 351119 432876 533670 657933 811131 1000000 1232847 1519911 1873817 2310130 2848036 3511192 4328761 5336699 6579332 8111308 10000000 12328467 15199111 18738174 23101297 28480359 35111917 43287613 53366992 65793322 81113083 100000000 123284674 151991108 187381742 231012970 284803587 351119173 432876128 533669923 657933225 811130831 1000000000 1232846739 1519911083 1873817423 2310129700 2848035868 3511191734 4328761281 5336699231 6579332247 8111308308 10000000000 
];
