A = [
5599434 5889351 57130956 7453329 6182277 6636588 7453007 6184281 5902258 5586771 5432473 5413820 5263129 5041853 4945868 4826403 4668656 4611095 4530191 4406984 4346633 4295513 4229667 4196387 4248059 5104455 5216133 5399764 6176470 5498508 5504224 5377374 4772757 4788722 4715675 4698047 4639522 4545410 4521839 4462545 4436316 4403129 4355646 4334790 4301693 4266719 4257063 4234529 4206888 4196135 4176209 4146659 4130422 4108301 4079948 4057193 4030363 3998658 3975677 3954315 3921787 3907216 3878481 3851563 3837922 3817547 3786704 3773774 3748900 3722484 3704316 3689085 3666970 3656057 3636111 3609263 3594287 3581282 3556533 3534459 3516813 3496974 3480950 3471135 3441424 3428092 3420159 3391260 3381579 3365165 3340720 3328705 3314553 3289518 3278826 3262484 3247399 3226845 3216923 3196841 3178185 3170855 3149393 3137637 3124794 3105468 3096179 3082765 3064793 3054737 3045512 3026293 3017677 3004538 2986213 2985741 2977852 2981353 2981136 2974624 2981760 2971721 2957858 2940115 2930455 2920649 2899073 2891160 2881445 2857724 2850807 2836845 2818374 2812225 2798944 2781400 2772341 2761568 2740285 2733138 2720265 2704094 2690742 2678358 2665388 2658854 2643778 2628970 2614996 2601368 2592056 2582022 2570457 2554528 2541219 2531623 2512742 2509237 2495828 2478931 2473577 2459097 2450986 2438400 2427906 2413112 2402576 2391385 2376210 2369045 2361540 2347233 2335600 2324986 2309358 2298272 2290068 2269730 2261736 2251608 2235495 2229294 2217053 2204563 2198386 2185646 2169673 2167032 2148471 2139960 2127340 2119180 2105946 2092449 2089986 2075102 2064283 2054981 2039712 2029107 2016410 2009820 2002661 1990801 1978011 1965378 1957542 1945152 1934531 1925740 1911622 1903031 1890669 1880240 1871049 1861693 1845881 1840147 1832426 1818803 1808085 1798439 1785575 1780304 1769120 1753448 1746262 1738249 1721399 1715944 1701981 1690053 1681668 1671288 1661429 1648301 1641082 1630447 1618941 1607479 1601037 1591787 1580482 1570521 1555621 1549950 1535981 1524790 1519532 1501134 1492801 1487048 1473165 1463412 1454004 1442311 1432204 1421708 1410743 1405204 1391201 1381850 1369479 1358978 1350480 1341378 1331910 1322156 1311714 1300838 1292677 1282767 1273065 1267706 1255627 1244455 1235246 1226238 1218723 1207794 1194033 1188394 1176012 1166931 1159415 1147948 1138110 1131808 1120249 1110495 1102402 1091636 1083442 1075842 1063688 1056960 1046650 1038568 1029035 1020311 1013146 1003288 995744 983780 977352 967638 959461 950338 944133 934447 927474 919392 910251 902719 897070 888090 877488 870740 864919 856028 848522 838012 832813 823678 816874 809689 802143 794391 788643 779034 774700 764505 756830 748909 743679 737500 728601 724207 717293 709164 703875 697179 689668 682725 677680 670901 667298 660047 649221 645782 641849 633269 628961 623381 616426 609752 607081 599212 593378 588213 583194 579650 574573 565800 563253 556771 550627 544695 539260 533462 529518 524423 518350 514531 509523 502586 497752 493601 488634 481922 478513 473882 470685 465378 460149 456902 451471 444482 440549 436763 430990 426054 422474 416877 415525 409967 405874 401078 396471 393853 387922 384203 380705 376259 372025 369067 364596 359941 356075 353031 350236 346091 342456 338287 334101 331037 326962 323082 319450 314316 311319 307753 304406 300659 297733 293263 290839 287561 284647 280387 277340 274230 270858 266972 265129 261835 258096 254247 250877 249076 246400 242806 239655 236553 235176 231665 228635 226414 223358 221543 218153 215164 212311 210896 207416 204689 201613 199297 197617 194075 192633 189083 186321 185234 182423 179392 177723 176452 173747 170246 169425 166011 163851 162008 159122 157078 155794 152689 150658 149152 146709 145490 143507 142464 139531 137827 136357 133510 132579 131068 128843 127322 125757 124014 122432 120116 117916 117192 115476 114519 112347 110064 109490 107473 105360 104329 102708 101664 100177 98821 97347 95656 94165 93127 92418 90508 89476 88170 86769 85384 84324 82945 81474 81096 79525 78931 77843 75802 75443 74226 72854 71788 71298 69903 69239 68146 67246 66276 64763 64537 63312 62162 61667 60618 60158 58934 58514 57870 56139 55801 54251 54551 53937 53248 52064 51359 50852 49518 49606 48692 47690 47508 46948 46083 45247 45045 43943 43827 43253 42079 41720 41522 40483 40141 39425 39402 38534 38362 37343 37139 36646 36089 35628 35591 35010 34451 34066 33834 32877 32936 32505 31532 31573 31200 30774 30039 30003 29347 29182 29008 28492 27876 27351 27309 26829 26643 26275 26108 25664 25325 25037 24777 24425 23872 23754 23720 23217 22905 22751 22701 22276 21852 21556 21495 21158 20984 20480 20180 20233 20040 19997 19752 19922 18980 19000 18880 18666 18471 18068 18010 17950 17597 17497 17296 17448 17054 17203 16829 16858 16672 16099 16142 15743 15583 15684 15186 15326 15168 14685 14615 14532 14491 14259 14107 13995 13603 13837 13590 13597 13540 13399 13217 13242 12960 12800 12620 12610 12369 12347 12241 12186 12057 11987 11937 11661 11482 11735 11467 11624 11254 11125 11252 11070 10977 10865 10776 10675 10628 10559 10469 10661 10639 10563 10301 10306 10152 9844 9953 9855 9999 9520 9643 9540 9515 9387 9529 9382 9033 9224 9240 9099 8920 9190 8782 8981 8945 9072 8892 8842 8889 8701 8798 8578 8563 8505 8397 8344 8673 8238 8317 8256 8202 8098 7947 7818 7889 7814 7651 7795 7983 7750 7581 7534 7503 7696 7451 7473 7452 7406 7337 7453 7469 7153 7129 6895 7095 7111 6921 7085 6949 6995 6700 6810 6805 6906 6847 6648 6812 6601 6901 6617 6619 6465 6594 6207 6620 6348 6279 6167 6344 6440 6229 6163 6255 6105 6235 6088 6086 6070 6178 6027 6173 6087 6029 6019 5994 6005 5748 6076 5905 5934 5992 5917 5769 5838 5806 5888 5866 5589 5537 5665 5709 5644 5804 5422 5482 5631 5604 5590 5423 5586 5504 5586 5523 5576 5539 5420 5406 5459 5446 5482 5336 5351 5191 5209 5339 5269 5267 5197 5014 4980 5083 5050 5155 5075 5041 5044 4987 5080 5060 5058 5030 4952 5010 4947 4817 4943 4816 4903 4760 4847 4969 4660 4684 4837 4632 4755 4666 4802 4493 4586 4572 4621 4629 4608 4661 4515 4677 4566 4578 4452 4458 4480 4379 4417 4360 4492 4449 4570 4475 4400 4367 4851 4284 4453 4694 4471 4397 4294 4320 4231 4093 4158 4156 4187 4138 4135 4134 4119 4098 4074 4006 3945 3944 4065 3813 3877 3880 3872 3703 3888 3769 3828 3642 3675 3806 3741 3726 3736 3701 3595 3691 3634 3721 3863 3685 3894 3660 3609 3639 3622 3693 3675 3534 3498 3592 3688 3560 3522 3468 3552 3431 3486 3385 3519 3340 3379 3337 3356 3269 3444 3405 3293 3298 3341 3427 3408 3270 3302 3197 3421 3331 3086 3259 3393 3322 3198 3286 3213 3301 3199 3392 3295 3364 3238 3373 3278 3321 3245 3202 3324 3300 3346 3103 3460 3545 3277 3134 3171 3275 3228 3337 3143 3191 3121 3037 3140 3173 3093 3053 2988 2925 2956 2858 2788 2936 2794 2815 2895 2903 2774 2802 2794 2816 2714 2817 2711 2751 2689 2767 2667 2715 2782 2670 2598 2687 2496 2573 2678 2648 2661 2691 2635 2665 2732 2589 2542 2702 2520 2583 2604 2581 2738 2544 2721 2649 2576 2672 2640 2510 2551 2555 2573 2485 2573 2527 2474 2637 2456 2506 2489 2495 2486 2658 2453 2435 2406 2444 2428 2382 2421 2449 2544 2410 2400 2356 2409 2455 2405 2371 2333 2315 2331 2330 2250 2324 2250 2228 2181 2230 2300 2213 2203 2268 2299 2169 2199 2118 2156 2149 2184 2138 2193 2050 2129 2108 2181 2277 2161 2151 2079 2067 2097 2063 2043 2046 1994 1974 2006 2037 1985 2035 1967 1956 1969 1971 1956 1966 1852 1970 1850 1836 1951 1898 1906 1891 1818 1866 1911 1883 1874 1849 1861 1891 1965 1929 1955 2008 2036 2052 2075 2071 2039 2139 2148 2098 2242 2103 1997 2074 2060 2193 2125 2043 1833 1983 1892 1911 1868 1858 1872 1928 1962 1851 1880 1756 1812 1850 1837 1868 1901 1727 1706 1813 1770 1760 1834 1730 1725 1693 1627 1653 1720 1640 1650 1680 1578 1721 1659 1692 1643 1587 1633 1730 1573 1589 1638 1532 1612 1570 1564 1563 1566 1553 1581 1551 1642 1609 1575 1544 1524 1541 1521 1550 1504 1567 1434 1447 1554 1554 1464 1538 1440 1506 1468 1494 1622 1516 1561 1480 1546 1498 1466 1528 1572 1372 1406 1459 1357 1410 1401 1470 1431 1493 1416 1477 1491 1425 1503 1414 1401 1373 1404 1366 1381 1417 1435 1439 1346 1377 1280 1377 1376 1345 1446 1389 1381 1355 1319 1330 1350 1296 1381 1264 1330 1322 1361 1336 1285 1382 1358 1312 1369 1318 1384 1402 1376 1344 1327 1274 1345 1365 1289 1432 1272 1347 1358 1291 1385 1278 1350 1315 1351 1382 1326 1336 1301 1390 1414 1357 1297 1345 1349 1272 1300 1223 1342 1346 1304 1248 1298 1266 1318 1245 1210 1294 1273 1210 1302 1307 1247 1289 1276 1346 1246 1272 1222 1277 1219 1267 1238 1256 1192 1238 1264 1268 1178 1263 1213 1235 1269 1231 1269 1224 1229 1194 1161 1223 1282 1279 1305 1184 1241 1140 1207 1218 1249 1161 1180 1216 1179 1209 1234 1146 1260 1187 1116 1184 1189 1137 1204 1194 1152 1208 1223 1124 1143 1136 1097 1194 1160 1192 1122 1146 1187 1182 1114 1099 1197 1084 1199 1104 1137 1102 1131 1108 1162 1166 1042 1092 1114 1131 1095 1033 1091 1046 1001 1083 1003 1106 1034 1034 1032 1039 1066 1048 1032 1018 1060 974 1037 1071 972 1039 1049 1291 1017 1000 1050 931 1034 1057 1029 1064 989 978 1063 999 993 1025 1010 1074 1097 1078 1050 1014 1018 986 1063 1012 1071 1048 1038 1099 1042 1031 1032 1059 1088 1036 983 1017 1053 1006 963 955 965 979 1048 920 1014 1029 894 975 978 986 978 1133 991 1055 1139 955 986 1001 1002 1000 1019 996 1052 980 1031 957 994 941 954 930 909 894 950 957 945 906 910 993 958 943 1008 938 889 962 950 995 849 875 838 881 898 808 867 805 882 857 836 826 860 868 758 807 760 838 807 824 815 872 824 781 859 802 836 755 757 782 726 767 726 724 763 775 768 758 732 787 750 751 746 800 743 759 784 777 719 731 716 731 676 765 732 708 680 709 735 762 717 744 781 742 720 732 677 742 747 735 714 710 683 687 692 685 682 679 742 749 714 740 718 682 685 709 659 684 685 740 722 743 707 747 762 736 682 694 669 770 679 1144 763 748 772 760 744 700 737 797 681 706 744 677 713 703 691 705 688 767 778 771 736 723 787 769 784 721 790 727 747 762 740 719 733 723 697 687 650 707 659 674 676 735 647 625 564 720 625 656 645 620 659 584 602 614 631 656 687 590 598 590 562 584 678 619 575 579 568 605 591 617 615 607 567 614 628 628 625 630 582 588 580 578 540 546 543 582 576 589 584 534 592 552 550 562 601 582 569 563 516 558 516 504 558 515 548 533 519 546 590 548 559 579 558 584 574 540 607 556 520 566 559 561 521 601 557 601 552 586 614 575 563 574 538 579 518 505 476 544 497 546 512 539 526 582 571 564 553 548 566 564 536 624 525 558 578 515 526 520 515 495 561 578 518 499 528 534 599 531 561 557 524 619 539 579 557 566 586 562 590 527 547 565 564 554 556 545 546 519 547 593 531 518 554 510 512 526 533 473 502 482 477 530 471 487 514 542 495 524 523 502 536 521 518 503 509 494 499 460 515 494 524 443 494 454 503 473 452 481 485 479 526 496 494 463 458 528 500 483 526 466 471 471 471 505 479 479 509 499 457 421 439 466 468 444 415 430 506 431 529 491 451 489 435 459 440 461 472 502 427 500 488 467 479 515 503 425 413 418 420 439 381 366 403 386 369 405 357 400 417 364 379 391 359 376 368 333 397 366 400 397 386 412 414 387 415 451 402 452 411 434 373 382 410 395 384 369 394 374 396 428 394 392 379 397 385 412 372 405 376 416 406 338 404 386 355 326 346 323 361 364 366 341 338 356 355 390 
];
B = [
0 0 0
 543995 297360 246635
 466889 267616 199273
 633097 366010 267087
 547647 314544 233103
 569856 339550 230306
 745589 447114 298475
 585289 367388 217901
 1148294 736866 411428
 766069 487281 278788
 492546 339986 152560
 1162215 808689 353526
 312371 220231 92140
 246756 180303 66453
 219624 159576 60048
 220787 149710 71077
 154761 106691 48070
 261155 177590 83565
 158277 116161 42116
 203413 145609 57804
 220173 162739 57434
 334198 241689 92509
 710259 497047 213212
 391372 291452 99920
 358631 269286 89345
 427532 325678 101854
 368146 280856 87290
 685001 526266 158735
 1045954 778698 267256
 329549 262197 67352
 368806 303310 65496
 396228 318225 78003
 503871 395668 108203
 443984 366958 77026
 419451 342892 76559
 402020 337408 64612
 287018 240002 47016
 480947 404175 76772
 306925 262472 44453
 453837 388658 65179
 403545 338037 65508
 473618 399138 74480
 571708 475135 96573
 564305 461950 102355
 531300 476221 55079
 433861 373446 60415
 401848 356199 45649
 460949 403267 57682
 597663 517263 80400
 490441 443020 47421
 430222 379218 51004
 553560 491075 62485
 491447 437661 53786
 424144 382655 41489
 859788 753381 106407
 547691 486730 60961
 599638 526071 73567
 546473 485427 61046
 568187 514208 53979
 922012 852508 69504
 495343694 473311674 22032020
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
3247 6750 118 261
704 1188 14 16
967 1482 32 32
1049 1952 36 54
840 1902 62 56
949 2404 155 87
4718 3401 456 224
9716 3935 845 487
26207 5042 3995 1460
75447 6962 9139 4032
165646 8650 12405 6898
389187 11933 18830 11657
831841 16304 28905 19254
1680188 23831 49776 34556
3028211 34804 70294 53291
5725170 54005 101778 84535
10755151 85126 145507 128465
16975912 136679 208670 195091
18413889 214070 299777 292799
16404059 314905 412325 409832
8245130 426792 540715 537827
1980144 548764 672267 670631
983158 693844 805834 802981
1010992 852880 943368 940457
1139071 1015370 1084049 1079857
1283511 1183729 1231829 1229028
1426764 1344979 1381060 1377741
1583825 1505147 1539815 1537645
1737655 1665788 1693712 1690517
1890989 1832301 1856260 1851753
2065165 1998021 2019206 2013092
2228687 2157111 2176696 2171195
2391790 2313700 2330861 2324240
2524655 2476090 2480385 2482312
2647404 2630094 2642232 2633752
2787358 2777089 2779496 2777360
2911053 2904984 2910194 2905193
3031643 3032578 3032829 3028690
3139785 3146690 3142390 3141976
3236196 3246153 3245547 3242241
3328754 3343447 3339749 3337757
3407707 3421850 3411219 3415159
3470289 3487296 3476715 3474805
3498815 3518194 3509147 3510758
3503787 3524489 3513465 3510588
3493705 3513020 3505898 3503342
3420272 3428314 3427089 3425585
3285149 3291794 3289013 3283981
3122611 3128953 3130935 3123456
2929602 2939306 2933919 2934222
2698103 2708471 2702062 2697728
2458285 2464473 2460152 2462790
2228899 2229116 2228189 2228817
2025179 2026645 2028352 2022271
1862481 1859901 1864326 1859239
1717827 1720539 1716602 1715486
1613616 1610273 1613181 1611151
1550332 1550607 1549047 1552473
1537005 1536107 1536316 1537066
1519705 1515146 1518470 1520730
1568851 1567940 1565919 1565078
1539547 1539661 1539002 1538039
1524194 1521134 1524076 1523858
1463942 1464345 1465211 1464472
1350051 1349790 1350340 1348675
1176223 1177513 1174883 1174532
923879 924598 927066 925018
661233 664219 664491 662152
426999 431224 432339 427118
237157 238098 238891 235864
91237 95370 95487 90763
16790 17566 16666 16297
20 61 73 28
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
