A = [
5443406 5724481 55517911 7245142 6008786 6451084 7244709 6013454 5739848 5432286 5283547 5267710 5121545 4905288 4812101 4696190 4542839 4486975 4408076 4288185 4229915 4179836 4116506 4083496 4134400 4971285 5081006 5260825 6020256 5359180 5366597 5241849 4652994 4669933 4598154 4582213 4523966 4433038 4410374 4352248 4328491 4296321 4250319 4230181 4197299 4159756 4150459 4128360 4097807 4087512 4066136 4036462 4021245 3999767 3970503 3948302 3922587 3891405 3868905 3847459 3816029 3802537 3774250 3748218 3735192 3715159 3684560 3672877 3646032 3621247 3602372 3587200 3565825 3556206 3536490 3511372 3496411 3484343 3460028 3438578 3421316 3402888 3386487 3376505 3348010 3335512 3327522 3299294 3288953 3273114 3248666 3238009 3224048 3200206 3188707 3173278 3158119 3137358 3128514 3109378 3091141 3084006 3062929 3052875 3039287 3020382 3010838 2998023 2979842 2970682 2960792 2942317 2933958 2921804 2903660 2902465 2893999 2896444 2896078 2889250 2894661 2884958 2871207 2853866 2844852 2834662 2814046 2806437 2797091 2774006 2767861 2753423 2735679 2729561 2716152 2699771 2691672 2680033 2658824 2652603 2640145 2624369 2612051 2600522 2586999 2580996 2566885 2551502 2538432 2524316 2515410 2505989 2494585 2479301 2466407 2457246 2439507 2436438 2424149 2407044 2401819 2388063 2380059 2367615 2358000 2343591 2333944 2323786 2308289 2301333 2294387 2281087 2269932 2259860 2244904 2234075 2226739 2206540 2199095 2189101 2173716 2166921 2155503 2143569 2136618 2124502 2108319 2106307 2087988 2080451 2068046 2061016 2047574 2035101 2032099 2017778 2007228 1998796 1984550 1973859 1961775 1955371 1947483 1937193 1925017 1913146 1904522 1893285 1883072 1873968 1860149 1852141 1839473 1829966 1820245 1811716 1796686 1790310 1783709 1770380 1759615 1750456 1738140 1732752 1722545 1707680 1700836 1692955 1677181 1671531 1658488 1646120 1638606 1627956 1618051 1605739 1598859 1588156 1576569 1565812 1559791 1550630 1539580 1529911 1514620 1509281 1496127 1485733 1480058 1462135 1454340 1448575 1434959 1425338 1416692 1405835 1395571 1385177 1375105 1370126 1356238 1346647 1335077 1324565 1316466 1307058 1298215 1289067 1278653 1267925 1260019 1250199 1241054 1235507 1223866 1212727 1204193 1195603 1188095 1177081 1163684 1158048 1146552 1137570 1130397 1119042 1110015 1103307 1092146 1082601 1074776 1064573 1056044 1048931 1037411 1030493 1020856 1012998 1003549 994902 987785 978544 971062 959118 953413 943618 935569 926558 920470 911121 904434 896366 887426 880432 874927 866016 855430 848745 843080 834598 826953 816730 811448 802766 796180 789194 781366 774158 768600 759348 755051 745024 737446 729822 725037 718701 710110 705588 699072 691102 686044 679378 672500 665672 660912 654077 650517 643280 633108 629447 625656 616818 612869 607430 600784 594475 591847 584011 578468 572732 568236 564666 559305 550682 547934 541959 535980 529555 524644 518892 515163 510065 504084 500454 495707 489110 484701 480116 475755 469282 465963 461098 458302 453232 447814 445026 439887 433129 428946 425457 419865 415084 411516 406256 404600 399344 395320 390609 386136 383669 377900 374194 370790 366327 362056 359136 354855 350471 346737 343429 340912 336764 333038 329319 324879 321778 318157 314261 311200 306056 302992 299816 296338 293213 290261 286089 283339 280185 277477 273169 270213 267206 264106 260131 258336 255019 251510 247742 244477 242603 239816 236291 232990 230190 228683 225336 222442 220123 217245 215633 212208 209282 206438 205080 201797 199208 196206 193926 192446 188792 187597 183946 181403 180215 177692 174740 173025 171451 168748 165705 164882 161491 159314 157580 154662 152814 151646 148516 146547 144982 142537 141445 139376 138257 135554 133684 132187 129503 128530 127198 125041 123354 121973 120401 118692 116484 114189 113309 111703 110664 108346 106409 105801 103776 101929 100934 99341 98245 96931 95631 94314 92598 91225 90108 89475 87716 86579 85330 83949 82636 81610 80271 78749 78473 76941 76121 75318 73400 72865 71760 70506 69427 68948 67712 67027 66015 65168 64104 62736 62563 61420 60240 59755 58767 58224 57186 56729 56059 54431 54075 52529 52843 52195 51573 50415 49750 49207 47869 47941 47065 46016 45865 45379 44422 43628 43405 42359 42199 41642 40478 40162 39998 38946 38603 37911 37886 37065 36911 35893 35764 35228 34608 34189 34157 33540 32994 32636 32453 31424 31525 31055 30130 30152 29798 29398 28680 28729 27923 27956 27622 27211 26691 26122 26122 25638 25396 25085 24928 24525 24212 23869 23617 23237 22742 22661 22530 22092 21838 21696 21655 21279 20871 20431 20441 20117 19971 19432 19108 19168 19005 18997 18614 18933 18045 17980 17879 17774 17464 17120 17131 17027 16641 16490 16162 16306 15922 16047 15642 15702 15555 14980 15023 14918 14724 14881 14355 14499 14323 13903 13785 13744 13685 13460 13298 13173 12829 13041 12796 12737 12771 12581 12430 12499 12143 12041 11883 11924 11640 11595 11519 11454 11271 11235 11179 10921 10746 10988 10781 10971 10571 10432 10550 10399 10316 10203 10131 10017 9967 9894 9766 10062 9886 9827 9629 9592 9444 9149 9169 9190 9311 8854 8946 8917 8872 8769 8891 8690 8396 8582 8618 8416 8287 8552 8179 8360 8320 8492 8301 8259 8329 8130 8180 7954 8026 7920 7861 7814 8042 7666 7709 7689 7629 7563 7412 7311 7337 7274 7123 7285 7441 7252 7043 6988 7014 7163 6937 6972 6959 6954 6830 6961 6859 6600 6641 6450 6634 6640 6482 6621 6461 6606 6278 6361 6331 6475 6425 6190 6363 6147 6383 6185 6188 6076 6196 5799 6189 5957 5894 5785 5978 6035 5864 5791 5845 5749 5852 5717 5752 5717 5784 5673 5770 5691 5622 5618 5557 5607 5351 5655 5484 5537 5564 5380 5368 5455 5451 5513 5456 5225 5204 5306 5357 5263 5400 5060 5130 5293 5238 5231 5040 5234 5111 5194 5165 5204 5156 5083 5008 5029 5047 5103 4993 5036 4858 4884 4921 4956 4967 4863 4686 4658 4707 4690 4797 4709 4707 4735 4684 4699 4701 4754 4723 4603 4611 4613 4549 4634 4493 4490 4360 4523 4516 4308 4374 4499 4258 4441 4289 4439 4196 4345 4324 4348 4398 4332 4398 4265 4433 4303 4372 4217 4222 4220 4144 4154 4114 4218 4187 4306 4203 4164 4120 4101 4056 4201 4397 4190 4146 4036 4069 3993 3831 3885 3917 3932 3849 3891 3884 3847 3826 3797 3755 3715 3723 3834 3598 3632 3665 3634 3493 3673 3554 3626 3435 3465 3574 3510 3498 3507 3495 3369 3435 3393 3408 3591 3379 3573 3343 3306 3358 3371 3411 3397 3310 3291 3374 3472 3335 3286 3246 3321 3205 3296 3204 3319 3174 3151 3144 3141 3044 3229 3213 3086 3081 3126 3249 3228 3062 3125 3003 3214 3134 2908 3083 3182 3062 2974 3093 2970 3069 2902 3145 3034 3114 2933 3083 3012 3004 2963 2886 3027 2985 2991 2806 3098 3201 2962 2810 2845 2929 2887 3012 2828 2874 2797 2748 2819 2878 2768 2762 2698 2659 2711 2618 2552 2704 2543 2590 2683 2645 2534 2580 2564 2607 2512 2601 2475 2513 2471 2552 2436 2497 2596 2466 2404 2456 2282 2389 2474 2424 2467 2490 2400 2434 2514 2398 2335 2447 2286 2341 2416 2371 2488 2329 2508 2448 2369 2449 2436 2279 2344 2326 2354 2268 2377 2318 2255 2290 2257 2313 2321 2303 2275 2174 2242 2237 2225 2259 2231 2212 2221 2282 2371 2235 2235 2182 2257 2270 2254 2197 2175 2163 2165 2182 2109 2155 2088 2069 2018 2070 2134 2053 2055 2101 2139 2022 2062 1979 2028 2006 2028 1997 2039 1907 1955 1955 2018 2135 1991 2021 1968 1933 1973 1943 1911 1912 1873 1854 1883 1914 1874 1906 1821 1818 1816 1857 1855 1830 1753 1855 1728 1702 1784 1780 1756 1750 1674 1710 1817 1799 1758 1747 1772 1777 1854 1808 1772 1805 1794 1817 1797 1759 1664 1814 1785 1723 1858 1785 1691 1747 1684 1815 1769 1770 1604 1755 1711 1692 1683 1667 1691 1750 1744 1668 1721 1627 1684 1703 1652 1706 1725 1590 1568 1662 1661 1622 1686 1600 1602 1616 1543 1569 1643 1551 1587 1600 1510 1661 1589 1623 1572 1510 1567 1665 1512 1516 1574 1474 1538 1504 1485 1502 1496 1487 1505 1468 1568 1519 1494 1469 1457 1457 1436 1481 1422 1478 1360 1382 1481 1465 1388 1450 1345 1418 1401 1420 1549 1435 1494 1423 1467 1436 1388 1447 1485 1297 1327 1378 1293 1347 1329 1407 1369 1415 1341 1409 1432 1367 1438 1349 1328 1318 1326 1293 1309 1349 1364 1369 1289 1315 1239 1320 1326 1277 1386 1331 1312 1297 1260 1269 1292 1253 1320 1219 1260 1262 1293 1276 1199 1317 1278 1247 1290 1247 1307 1317 1286 1272 1250 1198 1270 1291 1224 1354 1207 1272 1304 1216 1303 1208 1276 1246 1301 1312 1237 1284 1243 1321 1334 1274 1226 1274 1284 1199 1228 1140 1277 1291 1249 1182 1202 1200 1246 1179 1141 1217 1194 1140 1220 1239 1165 1225 1212 1292 1173 1230 1156 1209 1172 1198 1163 1172 1133 1154 1185 1178 1120 1190 1134 1157 1189 1166 1200 1142 1156 1117 1097 1131 1179 1210 1214 1130 1165 1065 1149 1128 1172 1082 1104 1140 1093 1131 1153 1039 1182 1102 1033 1110 1107 1055 1118 1110 1096 1143 1175 1082 1065 1073 1044 1145 1111 1145 1075 1105 1131 1126 1072 1053 1144 1031 1140 1060 1095 1053 1084 1057 1124 1127 1004 1062 1070 1082 1051 995 1040 998 964 1049 966 1059 1001 992 999 988 1032 1010 989 983 1030 938 1003 1027 929 1006 1015 1254 983 962 1000 902 1000 1025 994 1030 964 942 1028 956 944 988 965 1024 1050 1031 1009 964 966 938 1006 960 1022 979 979 1054 982 987 975 1006 1049 986 923 978 1005 938 924 909 915 936 1009 875 974 985 852 945 932 946 939 1089 940 1008 1091 912 935 950 959 961 972 939 993 926 972 906 938 881 873 882 867 842 898 901 903 861 866 944 900 903 955 879 840 898 894 937 796 832 781 833 846 756 820 750 820 800 770 759 811 818 711 759 695 781 753 780 756 814 770 711 801 741 783 708 705 721 667 707 680 674 714 728 721 706 678 735 699 713 700 757 699 708 732 733 674 690 678 695 637 709 652 665 640 680 698 724 673 701 738 717 688 682 650 692 719 700 666 657 639 645 651 633 649 647 704 705 665 704 676 649 645 661 622 630 649 694 670 699 663 704 716 690 621 641 621 717 634 1094 715 704 724 727 705 657 694 753 636 657 698 643 675 657 645 668 659 717 728 741 714 699 755 734 750 689 767 703 707 735 707 685 709 701 663 666 634 675 630 654 645 716 620 594 528 675 584 637 616 592 631 544 570 579 585 615 662 558 562 558 530 538 636 590 542 545 535 568 563 581 574 570 527 568 589 599 581 587 550 552 549 546 506 509 503 555 545 544 555 494 552 513 521 533 569 558 538 542 488 532 495 485 528 494 523 505 498 521 562 525 545 559 540 556 554 519 584 526 503 547 541 548 497 575 532 577 525 569 594 561 537 551 514 560 491 489 454 526 473 526 490 519 509 563 549 534 537 516 540 535 514 583 502 526 552 493 506 500 477 475 526 551 496 469 496 506 569 511 535 516 482 562 477 514 520 521 541 511 534 489 513 537 539 527 535 532 531 507 538 580 515 504 540 497 492 507 515 454 481 459 456 513 459 469 499 529 479 507 508 486 516 508 490 485 479 480 466 431 490 472 495 425 478 446 494 448 441 467 474 464 503 478 482 444 441 516 485 466 497 443 457 450 443 478 463 463 490 483 442 404 425 453 452 425 402 415 489 418 511 467 437 470 420 437 423 447 452 487 410 476 476 458 468 500 484 414 395 398 406 421 365 345 382 363 359 390 346 390 402 348 362 373 351 358 353 308 374 346 381 374 376 389 397 373 403 434 381 429 403 417 342 360 392 379 372 354 380 355 383 413 380 378 366 383 374 396 361 384 364 401 391 319 389 370 337 311 332 311 339 347 349 332 323 338 342 371 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
3161 6632 109 256
684 1167 13 16
925 1455 30 32
994 1906 34 50
789 1867 61 54
880 2360 150 86
4517 3344 449 220
9336 3868 835 475
25282 4962 3920 1437
73060 6800 8969 3965
160821 8502 12191 6772
378334 11692 18502 11465
810203 16006 28425 18920
1637709 23362 48942 33990
2956831 34122 69165 52461
5599153 53060 100050 83204
10526734 83582 143315 126503
16626969 134153 205476 192035
18042471 210076 295244 288399
16083949 309540 406232 403645
8090369 419802 532723 529787
1943151 539699 662108 660844
966106 682729 793980 791060
994675 839489 929354 926192
1121206 999102 1068214 1064093
1264172 1165213 1213995 1211384
1405815 1324355 1360840 1357951
1559996 1482642 1517761 1515440
1712372 1641061 1669271 1666694
1863547 1805386 1830204 1825709
2034403 1967850 1991036 1984649
2195544 2126035 2145696 2140383
2355510 2279326 2297084 2290100
2485640 2438586 2443110 2445216
2606761 2589560 2601835 2593706
2744480 2733813 2736294 2734649
2865287 2859242 2864525 2859610
2982566 2983923 2984087 2980417
3087479 3094330 3089836 3090114
3182724 3192634 3189933 3187295
3271644 3286592 3280889 3278990
3346350 3360278 3349235 3353212
3406079 3422541 3411885 3409862
3431275 3451077 3441767 3442497
3433705 3453722 3443518 3440471
3419445 3439131 3431575 3429517
3344156 3352707 3350513 3349958
3209090 3216168 3213343 3208797
3049595 3056054 3057633 3050481
2860175 2870109 2864011 2865512
2631188 2640870 2635499 2630887
2393544 2400904 2396236 2399036
2172059 2172127 2170793 2172325
1973155 1974841 1976432 1970700
1813868 1812518 1816391 1812021
1676225 1679107 1674849 1674177
1576377 1573876 1576381 1574376
1516665 1517572 1515341 1518616
1505635 1504674 1506221 1507152
1490033 1485893 1488566 1491161
1542341 1541548 1539428 1539388
1512065 1511527 1510935 1510514
1497314 1495033 1496421 1496888
1437610 1437952 1437578 1438542
1325717 1325642 1325368 1325287
1154853 1155995 1153673 1153944
905606 905699 908042 907104
646248 647793 647674 646589
412414 414211 415929 412152
226765 226305 227620 225987
80780 82378 82394 80145
13193 13514 13487 13471
0 12 9 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
