A = [
1315706 1299080 7049171 1161724 1125451 1061793 1046641 1029857 1031999 1032531 1054423 1090608 1137176 1195080 1258910 1334158 1409370 1490902 1573693 1654725 1734331 1813233 1887257 1952805 2023377 2312918 2375440 2423631 2689951 2515491 2596300 2629648 2442567 2509117 2497003 2503889 2486249 2432384 2409185 2371478 2338818 2308242 2271379 2246335 2220549 2191164 2175568 2150090 2127969 2109925 2092441 2072551 2053987 2039942 2022312 2008218 1997610 1982198 1967321 1949451 1942846 1925009 1925403 1909648 1901577 1902133 1892281 2018479 2018756 2011402 2142218 2134149 2127170 2117758 2092899 2076155 2058465 2047079 2026784 2005709 1988092 1971660 1949156 1930255 1915041 1895747 1876948 1860961 1840200 1821020 1804831 1785416 1769090 1746867 1733536 1711149 1691969 1670707 1652480 1634249 1614865 1594467 1576696 1556671 1538510 1521642 1504484 1485161 1468870 1449784 1429340 1413311 1393115 1379449 1362978 1344247 1327403 1314707 1296628 1280904 1265451 1247241 1234504 1219884 1201835 1186241 1172326 1157597 1142775 1127259 1112985 1099412 1085138 1069904 1055487 1043069 1029653 1014820 1002296 988754 975932 960525 949191 935523 920726 909226 894834 886776 873367 862030 849892 839477 828053 817202 806196 796928 785043 773554 763552 748943 739346 730442 721440 707889 700979 692065 682588 673490 662110 654637 646356 635294 626557 618121 611195 601156 592646 585244 575933 567859 559639 551609 544588 537026 529080 522977 514400 505592 499325 492844 486483 478496 471973 465338 457297 450482 443674 436989 431750 424081 418005 412991 407421 399939 395504 389335 384217 379188 372295 368323 361090 356429 351921 346400 341695 337297 331433 325972 321223 316654 312491 306675 302438 299490 294119 289679 286525 282239 278271 273951 269486 265961 261446 258347 254247 250238 247601 243880 239368 236304 231808 229659 225090 222492 218989 215790 212153 208657 205567 203299 200417 197084 193885 190681 188122 185644 182174 179145 177110 174731 171179 169610 167370 164400 162155 159371 157632 155890 152173 150565 148106 145658 143397 141704 140499 137411 135518 133269 131094 129438 127229 125888 123284 122408 120228 118144 116905 115273 112497 111149 108887 107403 105854 103933 103116 101342 99802 97939 96425 95414 93704 92124 91504 89966 88457 87369 85733 84183 83215 81906 80242 79630 78343 77475 76225 74584 73488 72841 71812 70397 69608 68916 67125 66286 65526 64204 63761 62927 61658 61162 60093 59107 57884 56916 56273 56079 54906 53738 53325 52456 51646 51105 49998 49524 48886 47989 47104 46945 45959 45232 44581 44052 43284 42911 42073 41557 40857 40532 39726 39116 38550 37896 37272 37019 36416 35998 35410 34852 34522 33789 34049 32890 32651 31994 31864 31094 31160 30302 30146 29653 29225 28817 28360 28036 27637 27260 27127 26691 26256 26091 25251 25332 24855 24672 24582 24285 24102 23399 23181 22844 22780 22166 22008 21714 21458 21022 20990 20958 20394 20136 19819 19584 19714 19186 18535 18703 18410 18096 17917 17916 17682 17501 17284 17156 17020 16613 16467 16354 16051 16035 15924 15496 15441 15382 15150 14995 14832 14422 14415 14688 14163 14111 13774 13658 13677 13449 13305 13133 13034 12895 12686 12549 12508 12648 12440 12304 12193 11982 11839 11941 11766 11450 11416 11448 11293 11284 11029 10951 11049 10694 10761 10602 10588 10587 10483 10260 10154 10093 9984 9779 9882 9726 9759 9545 9600 9538 9472 9152 9194 9058 9127 9002 9073 8993 8996 8792 8781 8560 8563 8535 8426 8329 8247 8241 8214 8030 8028 8118 7949 7960 7695 7742 7882 7795 7681 7470 7411 7357 7424 7435 7251 7084 7260 7285 7135 7134 6932 7078 6863 6979 6966 6729 6742 6677 6892 6631 6646 6442 6561 6470 6379 6159 6318 6329 6241 6158 6184 6132 6128 6091 6064 6126 5936 6023 5928 5878 6024 5888 5797 5659 5781 5718 5752 5619 5551 5519 5459 5637 5472 5486 5446 5507 5363 5352 5294 5362 5306 5360 5165 5071 5115 5134 5125 5103 5092 5107 4976 4975 5046 4931 4875 4819 4943 4964 5003 4934 4761 4816 4855 4650 4793 4680 4656 4690 4665 4570 4555 4622 4594 4540 4405 4454 4352 4493 4361 4558 4479 4386 4321 4320 4288 4266 4225 4140 4116 4065 4083 4086 4003 4062 4181 4117 4007 3945 4085 3939 3879 3887 3822 3863 3868 3770 3817 3794 3824 3819 3838 3729 3699 3718 3554 3656 3546 3557 3661 3566 3548 3657 3562 3526 3475 3505 3433 3348 3386 3465 3399 3360 3365 3410 3377 3467 3300 3165 3329 3247 3253 3251 3086 3239 3228 3115 3169 3080 3120 3119 3129 3119 2909 2860 3028 2960 3005 2944 2886 3023 2832 2852 2887 2905 2830 2838 2757 2829 2754 2838 2772 2709 2691 2705 2737 2675 2637 2621 2744 2579 2669 2748 2618 2604 2525 2610 2560 2597 2678 2421 2476 2545 2613 2465 2448 2514 2467 2442 2459 2374 2495 2454 2493 2366 2401 2434 2404 2451 2462 2379 2335 2350 2371 2334 2302 2261 2296 2168 2256 2268 2185 2255 2160 2103 2191 2111 2144 2118 2093 2158 2142 2034 2026 2094 2058 2055 2068 2062 2120 2065 2022 2089 2129 2152 2095 2108 2259 2153 2110 2289 2240 2272 2266 2460 2356 2446 2439 2574 2491 2510 2468 2349 2432 2341 2283 2327 2219 2099 2045 2036 2098 2034 2038 1995 1978 2056 2019 1816 1804 1813 1727 1714 1774 1710 1711 1674 1659 1680 1681 1636 1634 1662 1683 1593 1645 1669 1607 1590 1557 1595 1518 1521 1601 1546 1560 1545 1490 1490 1499 1511 1484 1462 1501 1467 1534 1510 1506 1414 1489 1489 1491 1357 1422 1451 1399 1371 1403 1392 1403 1382 1412 1329 1371 1371 1373 1374 1322 1385 1350 1346 1345 1345 1322 1399 1404 1369 1396 1348 1374 1279 1348 1336 1330 1421 1402 1368 1401 1401 1462 1396 1471 1415 1572 1575 1474 1521 1557 1590 1622 1509 1521 1498 1451 1576 1650 1618 1554 1538 1405 1452 1248 1224 1188 1117 1177 1206 1122 1140 1200 1142 1230 1205 1170 1146 1158 1221 1122 1118 1164 1153 1080 1065 1073 1052 1042 1063 1058 1088 1008 1105 1006 986 1022 1005 1002 997 948 957 1056 920 953 933 892 931 927 904 961 911 909 914 866 935 876 852 916 860 892 908 867 821 871 869 909 901 908 852 845 884 870 852 793 810 905 847 812 853 841 800 802 841 856 786 889 893 910 868 906 846 864 879 832 951 928 905 862 888 925 946 833 836 895 874 865 901 909 932 885 975 1034 1050 1047 1082 994 1054 1137 1109 1072 1041 1089 1052 1115 1081 1102 1059 1121 1028 1099 1071 1229 1075 1185 1210 1107 994 1072 1120 1081 1011 1070 1051 1037 939 997 894 910 895 864 862 786 842 871 804 801 758 695 731 748 694 774 675 632 628 595 643 580 622 602 519 529 512 501 577 502 505 469 494 491 483 515 528 481 482 504 482 483 447 478 482 429 450 459 470 471 463 433 438 449 488 442 459 409 411 416 428 431 456 462 473 420 405 442 414 459 439 408 429 452 392 374 369 378 391 375 388 400 413 410 396 373 379 406 361 392 385 433 399 375 372 389 371 420 390 367 344 368 358 347 369 342 323 351 350 390 373 327 318 358 341 343 366 325 352 345 361 352 363 350 347 313 307 356 356 340 356 325 362 310 337 329 330 327 329 309 330 287 296 330 327 302 309 319 294 318 314 287 288 322 304 287 270 330 296 286 308 306 277 270 307 268 290 254 262 235 279 268 260 271 302 253 274 276 268 236 255 259 257 258 245 251 226 260 265 203 256 257 237 244 277 244 225 257 222 242 230 246 228 251 247 234 241 233 209 207 241 238 226 231 221 237 227 222 234 250 231 237 216 208 219 217 247 212 215 184 215 178 194 202 203 222 194 183 196 207 195 231 217 195 229 207 184 193 200 180 202 200 190 189 202 203 196 210 199 198 185 179 184 152 198 195 186 194 202 159 164 166 173 173 190 207 179 180 184 175 186 177 172 172 161 175 170 177 155 187 193 156 189 158 172 151 148 170 161 162 173 144 153 130 148 165 155 171 164 160 157 169 154 153 167 150 139 153 127 146 160 159 136 144 126 146 153 142 130 148 157 146 131 152 146 138 132 122 145 131 139 124 154 134 155 132 133 155 127 118 144 121 135 114 128 116 137 140 123 120 117 113 133 104 141 138 130 135 140 138 105 128 98 128 126 118 118 113 109 133 123 106 129 112 114 101 91 115 97 98 121 101 97 117 110 109 122 115 121 113 115 97 110 107 112 107 122 92 112 100 103 104 92 78 104 116 99 100 107 94 111 87 101 85 102 89 104 92 93 113 90 123 111 102 95 85 104 90 91 83 97 86 87 103 106 100 96 71 102 108 93 87 87 100 98 96 82 88 78 90 102 93 80 61 80 87 79 92 104 78 81 84 78 78 102 84 84 85 78 72 83 104 96 95 95 79 76 86 77 82 90 72 79 69 65 76 65 57 74 71 71 75 68 81 54 64 65 60 68 70 72 66 72 72 52 49 71 68 74 81 56 68 72 71 74 65 66 56 62 54 65 55 72 71 65 73 59 61 63 54 50 50 56 66 56 62 57 56 56 62 61 61 64 60 48 63 68 59 68 65 67 51 64 54 66 58 63 71 63 71 68 50 66 73 55 69 51 66 47 48 42 50 55 50 66 41 62 47 56 49 56 53 65 50 45 45 55 39 46 53 50 53 58 62 51 47 45 49 45 58 56 53 52 50 41 49 56 56 50 44 52 45 43 43 50 40 39 52 43 40 45 37 36 36 32 40 36 43 34 46 25 38 47 36 35 44 38 24 35 41 46 36 41 37 42 25 25 37 41 31 27 38 40 31 34 30 29 38 44 33 33 32 32 31 30 46 39 31 37 32 34 32 30 25 27 30 27 33 21 25 27 18 26 27 29 35 33 28 31 33 34 22 40 35 45 30 30 27 16 33 31 34 32 28 25 27 33 29 24 26 32 18 25 25 25 34 28 28 21 31 27 35 31 20 26 29 20 21 25 25 22 26 26 22 22 29 27 19 25 22 32 16 19 24 17 25 26 22 27 25 18 27 16 26 18 27 27 31 23 16 18 18 29 20 24 22 16 16 28 21 28 17 19 19 12 16 17 21 19 14 17 20 23 22 23 16 22 25 27 17 22 21 23 18 18 23 18 18 16 15 18 16 22 18 16 24 21 17 20 19 19 12 14 16 21 20 15 16 24 17 14 13 19 13 19 16 21 17 13 14 12 11 7 15 14 12 19 13 16 24 14 13 17 18 16 15 21 18 26 18 19 18 10 17 19 14 16 16 17 11 10 13 11 18 11 14 14 15 8 19 17 18 20 33 17 13 23 12 16 15 17 17 6 19 9 11 16 11 11 22 12 15 20 9 20 9 10 9 10 9 10 11 14 10 10 24 14 13 16 13 16 9 9 11 12 18 9 17 12 19 18 12 11 13 10 13 14 14 9 16 10 
];
B = [
0 0 0
 841836 438269 403567
 931498 512523 418975
 767085 434462 332623
 1264681 790294 474387
 934681 595423 339258
 700228 463751 236477
 642806 431927 210879
 493674 333379 160295
 397636 272041 125595
 315535 216814 98721
 363938 251545 112393
 417495 289801 127694
 421250 293207 128043
 911884 647119 264765
 646763 465656 181107
 627257 457800 169457
 555153 411145 144008
 571567 429013 142554
 596014 448148 147866
 538687 405957 132730
 765782 575134 190648
 676561 512054 164507
 646890 490716 156174
 581964 442644 139320
 646956 492360 154596
 622756 476642 146114
 779771 596197 183574
 588568 452128 136440
 735933 564334 171599
 726934 558120 168814
 699306 537962 161344
 774682 597242 177440
 769252 592894 176358
 985289 759331 225958
 768132 594364 173768
 874047 676053 197994
 1853913 1431247 422666
 840316 651118 189198
 1007334 782313 225021
 1670865 1293347 377518
 1040656 808051 232605
 1586341 1230566 355775
 865072 674524 190548
 1060381 826717 233664
 1645288 1278421 366867
 1050144 820922 229222
 1604913 1249584 355329
 1097053 857124 239929
 1599202 1247375 351827
 1047549 821980 225569
 1579991 1235109 344882
 1185483 927936 257547
 1585308 1241502 343806
 1087981 855703 232278
 1708548 1339211 369337
 1586640 1244695 341945
 1085347 856300 229047
 1603833 1261065 342768
 946804 748388 198416
 106913892 86805515 20108377
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
84 142 68 10
11 27 2 2
17 43 2 2
8 48 4 5
17 56 3 5
24 76 12 6
204 79 18 16
1579 75 28 28
28804 115 45 27
262831 159 224 69
826898 191 1633 347
1932710 262 2521 1047
3559913 369 3288 1863
5186954 598 4764 3425
5816444 1075 7074 5802
5627752 1988 10739 9892
4531365 3446 15296 14877
3068587 5821 21265 21167
1644472 9592 29446 29665
568927 14866 39930 39791
136204 22328 50782 51311
73446 32621 63405 63453
80337 47267 78361 77951
94316 66192 94795 95660
112333 89928 114414 114263
134365 116403 137968 138358
160613 146662 165176 165647
190389 178881 195729 195778
222079 212566 227246 227585
256034 247589 260854 261302
289370 280144 293118 293508
320422 310803 322015 323379
349365 337972 347790 350857
366531 360227 371688 372374
382238 380539 390278 390080
396767 396034 405235 405280
407601 409327 416413 418344
422192 422100 428943 431126
435131 435076 441320 442337
449487 450028 454582 456486
465344 465342 471219 471630
483677 483757 489200 491371
503252 505325 511360 512082
529013 529943 533219 534785
553774 556113 559295 560916
578336 579882 583171 584536
604708 603627 607488 607724
621864 623066 626058 627467
636904 637361 639329 638721
642924 644601 643947 645366
642724 642845 641784 645839
631883 633086 632138 634252
614378 615877 614870 615217
585431 587586 585144 588242
554417 555011 552975 554553
515443 516775 516486 515835
476148 477714 474885 476855
436197 436822 436137 436514
397095 397186 397402 397733
364328 364457 363610 363415
334671 334856 333653 334838
314113 313661 313785 314593
298131 297699 297845 299179
287296 287188 285994 286745
287932 287879 287408 288575
303001 303056 301753 303571
323500 323115 322920 323880
351136 349510 349648 351187
390669 390643 391367 391269
438713 437588 437151 438251
500100 500152 499130 500958
533610 533261 534476 534591
568814 566915 565724 569245
588854 586788 585755 588529
579414 580181 578799 581995
526410 527808 526011 526985
439140 441028 439318 440592
308614 309373 308333 308697
160659 160638 160558 160668
58195 58338 58653 57959
9061 9101 9238 9148
57 72 58 69
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
