A = [
1295090 1275343 6700926 1124446 1077224 1017165 1004575 982675 982468 981241 995788 1025158 1063401 1108823 1162822 1221290 1285181 1350446 1423001 1488795 1554774 1618074 1685263 1732624 1790912 2027596 2068656 2109320 2318021 2171031 2236701 2261591 2103298 2154731 2138734 2141303 2125172 2073834 2053632 2017291 1990238 1963490 1929320 1907131 1884934 1860704 1842720 1821780 1804595 1791054 1771677 1754085 1739438 1726277 1710426 1697820 1686378 1675415 1662008 1648100 1637404 1625680 1624809 1612294 1602639 1602410 1593523 1694972 1694527 1687111 1788859 1786266 1776851 1765600 1746390 1732317 1716291 1700620 1685439 1671151 1651950 1638865 1622787 1606669 1591463 1574566 1559457 1544167 1527475 1513008 1497467 1483401 1467307 1450037 1435965 1420157 1401980 1386821 1370917 1353100 1334151 1322398 1306725 1287316 1275063 1257823 1244912 1230592 1215582 1201163 1184727 1171198 1153737 1141696 1127470 1113164 1100267 1086938 1074485 1062536 1048131 1035939 1022961 1010075 996143 983986 974506 958709 948451 938077 924367 912342 902563 889511 879558 867848 855234 845031 834213 822901 813483 801382 791954 781189 771062 761850 751661 740771 732122 722176 713249 703792 693434 684306 676843 669201 659498 652283 643672 633532 625560 617325 608990 601393 593466 585809 578278 571383 562949 556281 550100 541805 534998 527278 521084 515646 506954 501105 494886 488365 482142 475390 468191 462523 455519 451197 443394 439815 432315 428718 421089 417102 411189 404028 397800 393790 388180 382277 378287 372135 368340 363055 357817 354215 349169 345118 340578 336259 331357 328237 323328 318765 314921 309831 306058 301299 298081 293194 289887 286663 282585 278756 274512 270550 268545 262888 260131 256405 253046 251562 247887 243790 241125 238159 233718 230873 228242 225826 222374 220249 216290 212997 210616 207909 204992 201909 198985 197656 194491 192175 189207 186594 183902 181282 179588 176445 174616 171933 169862 167156 165224 163783 160602 158490 157290 154879 152884 151413 148747 147001 145598 143510 140962 139755 138037 136191 134178 132087 129164 128676 127063 125104 123604 121693 120140 119218 117264 115098 113681 112482 110817 110231 108629 106293 105213 103415 102596 100739 100074 98708 96888 95742 94144 93866 92513 90810 89399 88828 87320 86059 85032 83988 83307 81530 80834 79826 78517 78377 76210 75858 74657 73921 72753 71873 71344 69632 69117 68104 67129 66600 65653 64752 64061 63052 61913 61216 60758 59632 58741 58359 57835 56527 56245 55513 54755 54068 53543 52688 51983 51032 50619 49614 49107 48446 48397 47542 47243 46202 45403 45110 44542 44022 43510 42990 42217 41626 41281 40732 40208 40068 39239 38933 38073 37494 37519 37005 36630 36132 35479 34616 34895 34426 33772 33403 32911 32861 31753 31946 31343 31156 30659 29988 30083 29783 29496 28790 28475 28138 27996 27528 27289 26745 26631 26227 25898 25465 25597 25051 24917 24569 24027 23972 23552 23327 23152 22353 22713 22205 21904 21561 21596 21220 20912 20866 20550 20533 20174 19751 19877 19648 19487 19129 18576 18363 18352 18266 18016 17778 17654 17491 17140 16787 16787 16663 16539 16265 16205 15899 16016 15427 15578 15153 14809 14972 15088 14631 14414 14408 14404 14157 13865 13775 13534 13686 13304 13536 12963 12941 12900 12919 12442 12521 12584 12310 12141 12132 11802 11678 11735 11699 11479 11410 11462 10936 11057 10933 10870 10693 10605 10479 10567 10469 10292 10369 10186 9957 9935 9825 9605 9645 9514 9290 9275 9310 9167 9009 8824 9089 8697 8831 8686 8431 8436 8367 8278 8110 8271 8161 8173 8030 7966 7892 7766 7841 7727 7459 7584 7489 7506 7417 7207 7183 7247 7174 6994 7125 6916 7076 6894 6530 6815 6683 6606 6623 6451 6342 6337 6410 6308 6301 6116 6240 6138 6053 6065 5967 5792 5848 5896 5646 5637 5678 5589 5475 5796 5586 5560 5506 5333 5458 5359 5422 5366 5233 5262 5164 5296 5130 5090 5064 4941 4999 4967 4787 4886 4812 4811 4941 4831 4625 4755 4699 4611 4623 4646 4591 4597 4495 4553 4307 4406 4360 4278 4370 4255 4377 4175 4302 4178 4048 4207 4194 4040 4091 4009 3921 4115 3936 3876 3986 3948 3795 3913 3826 3805 3824 3847 3841 3794 3757 3763 3630 3607 3728 3548 3539 3555 3449 3555 3481 3318 3396 3373 3416 3413 3420 3442 3263 3262 3231 3273 3184 3298 3243 3167 3114 3254 3176 3215 3055 3041 3066 3099 3074 2997 3105 2963 3016 3066 2949 2912 2932 2930 2874 2738 2801 2820 2810 2812 2840 2704 2706 2764 2782 2728 2681 2795 2688 2659 2598 2667 2591 2566 2561 2501 2568 2536 2640 2571 2525 2539 2489 2396 2470 2402 2441 2336 2457 2387 2384 2367 2311 2398 2350 2282 2198 2308 2290 2222 2249 2338 2287 2252 2233 2172 2224 2199 2200 2114 2133 2167 2184 2108 2097 2055 2095 2091 2110 2136 2100 2036 2056 2125 2019 2081 1974 2014 1976 1933 1960 1965 1979 1919 2043 1958 1815 1883 1845 1907 1915 1829 1909 1821 1864 1877 1791 1814 1816 1796 1758 1757 1797 1820 1778 1742 1790 1707 1746 1802 1843 1824 1927 1790 1914 1858 1987 1910 1992 1966 2008 2164 2119 2187 2254 2154 2151 2179 2078 2137 2091 1914 1935 1988 1870 1820 1812 1830 1771 1769 1729 1667 1777 1739 1483 1622 1536 1496 1393 1448 1440 1412 1391 1512 1447 1395 1436 1462 1518 1395 1404 1419 1371 1362 1380 1404 1343 1357 1314 1329 1377 1358 1281 1348 1296 1266 1255 1335 1280 1277 1285 1270 1235 1340 1218 1262 1173 1251 1233 1243 1215 1269 1222 1165 1236 1155 1207 1268 1203 1193 1198 1226 1163 1122 1135 1216 1176 1166 1161 1178 1187 1181 1118 1150 1185 1174 1174 1231 1084 1127 1189 1154 1200 1186 1206 1198 1282 1231 1201 1316 1366 1298 1383 1374 1397 1446 1375 1334 1399 1325 1416 1455 1422 1358 1242 1264 1264 1028 969 1025 982 1048 1023 1021 1026 1021 1015 957 1026 1003 1024 1003 950 992 1038 924 946 962 984 933 908 933 914 940 861 931 932 914 823 885 862 882 850 896 795 797 846 816 792 756 767 777 766 791 828 763 797 705 741 753 807 781 787 757 758 724 802 762 759 741 734 745 757 681 730 729 730 739 694 748 740 689 714 711 753 759 684 699 785 709 715 713 731 763 744 766 761 777 771 828 777 742 755 761 790 798 805 786 771 767 835 810 823 820 876 938 890 948 928 927 988 985 1061 970 988 1029 966 1026 1032 1016 1007 1038 1003 972 1013 1105 1020 1168 1115 996 951 980 1032 987 999 959 954 935 884 894 779 807 775 836 744 758 739 754 762 687 684 617 655 655 656 698 609 585 568 504 516 505 548 495 427 454 448 442 425 441 440 445 458 392 401 421 378 394 396 398 410 445 432 398 397 383 366 387 366 391 394 373 378 389 385 350 387 374 380 390 357 378 411 340 368 361 354 360 371 376 393 340 348 354 396 375 355 334 324 381 355 367 360 351 367 364 326 356 312 346 320 356 328 303 283 319 305 294 319 299 302 281 352 294 315 275 298 359 302 334 300 288 302 320 328 302 307 296 287 305 316 325 297 287 295 294 276 310 288 291 283 292 239 304 270 267 269 270 254 316 270 284 248 260 304 255 268 277 256 284 261 247 258 237 247 286 244 268 264 261 235 269 253 279 261 237 244 230 215 225 204 227 272 250 229 239 214 213 179 232 212 238 231 255 189 221 199 214 229 197 233 200 197 242 196 229 221 197 191 198 199 229 188 197 190 197 222 184 222 203 179 199 222 190 189 195 198 187 214 191 200 188 182 175 172 173 203 195 163 180 159 187 184 166 164 205 162 182 157 144 155 174 186 188 186 181 182 171 169 163 181 176 178 169 188 170 191 171 157 182 152 174 138 174 153 156 150 135 140 161 158 156 157 162 145 144 147 123 140 123 140 157 164 127 149 146 119 140 127 116 123 155 151 143 126 149 142 134 148 156 139 134 131 136 140 153 115 150 133 132 129 131 141 122 124 138 144 139 122 135 106 114 124 119 107 119 140 113 125 145 103 131 135 105 121 102 106 100 128 127 136 107 115 100 126 99 110 108 118 97 100 123 119 113 105 124 124 107 109 115 93 104 122 107 89 84 114 106 107 98 113 83 107 100 89 115 99 91 95 99 117 94 88 96 111 105 94 91 77 88 81 85 94 84 97 98 88 92 85 104 92 82 85 76 93 91 97 97 113 91 81 89 81 90 88 90 78 87 74 83 71 94 67 93 74 79 100 88 86 93 86 80 78 86 76 75 92 90 80 91 92 86 87 66 97 90 89 92 88 77 84 76 73 84 78 82 53 71 67 65 91 71 87 69 86 65 78 76 72 71 84 92 72 79 81 73 70 72 83 89 72 63 75 76 80 70 85 73 69 53 68 73 70 58 49 66 65 59 63 66 85 51 56 58 58 59 57 57 58 58 68 62 73 51 45 65 76 66 54 55 52 56 53 50 57 53 41 53 56 61 52 54 63 43 50 49 54 62 55 54 49 49 45 52 51 52 49 54 54 52 50 44 44 49 43 70 54 52 36 57 55 52 51 55 57 42 58 48 44 52 48 65 55 50 50 68 47 48 46 39 52 49 40 46 51 39 46 39 41 48 33 52 39 43 56 44 54 44 35 42 43 49 33 43 32 51 44 46 42 39 47 42 44 40 35 31 43 33 42 36 37 42 39 38 46 40 44 40 40 29 38 40 36 29 37 37 39 31 40 33 31 41 29 33 41 46 33 31 31 39 33 37 28 34 32 39 32 31 29 35 40 34 33 30 25 38 30 46 36 24 24 31 21 31 21 18 22 34 25 29 23 20 29 27 26 16 27 32 20 28 33 30 38 21 25 20 17 16 17 24 18 14 21 31 21 25 28 26 24 17 22 26 25 25 29 32 26 28 22 15 28 28 22 23 24 20 27 30 25 21 19 23 19 26 20 16 29 33 21 28 20 22 18 14 18 17 17 18 18 32 16 24 18 27 20 19 21 17 23 15 14 21 15 21 26 22 25 20 19 20 15 14 15 15 13 18 22 17 14 21 21 19 17 16 9 13 20 24 14 10 17 16 20 20 17 17 15 14 13 23 13 10 14 15 19 8 10 17 9 12 21 19 13 15 8 15 17 15 9 20 16 11 16 15 11 15 15 16 23 18 12 17 9 9 19 21 13 8 10 16 16 14 14 12 12 12 20 11 8 11 15 10 16 10 18 14 16 11 21 11 12 19 15 11 6 11 14 16 6 10 11 13 11 9 18 16 12 22 12 9 13 13 8 18 16 8 17 14 11 14 4 15 14 11 11 14 11 13 12 18 10 15 15 9 11 12 9 8 13 9 10 12 11 10 13 11 12 12 14 8 11 14 14 10 14 11 10 11 11 15 14 12 8 10 2 9 15 12 9 7 11 
];
B = [
0 0 0
 759003 368504 390499
 846466 435060 411406
 685283 361537 323746
 1144934 672363 472571
 834636 498147 336489
 608951 378712 230239
 561577 354138 207439
 424866 269044 155822
 339572 217857 121715
 270170 174190 95980
 319846 207895 111951
 373968 243713 130255
 379809 248481 131328
 837787 562051 275736
 587854 398617 189237
 564586 389413 175173
 493210 346008 147202
 507027 360407 146620
 525194 373780 151414
 474145 337573 136572
 685437 488175 197262
 605360 433101 172259
 573012 411437 161575
 515653 372041 143612
 570956 412329 158627
 550525 400213 150312
 687720 498688 189032
 521370 380056 141314
 651005 474023 176982
 645461 470521 174940
 613933 448778 165155
 681975 499831 182144
 678176 497044 181132
 857460 628835 228625
 675857 497364 178493
 766582 563580 203002
 1558171 1145915 412256
 737427 544540 192887
 871985 644619 227366
 1408264 1039774 368490
 904079 668588 235491
 1340963 990987 349976
 758551 563080 195471
 918940 682153 236787
 1390698 1031786 358912
 907142 676149 230993
 1353451 1005516 347935
 949386 707852 241534
 1348020 1003513 344507
 905996 677511 228485
 1331494 993387 338107
 1020494 762556 257938
 1337967 1000976 336991
 939456 705706 233750
 1439283 1078809 360474
 1339826 1004661 335165
 934737 704452 230285
 1353687 1016519 337168
 829243 627009 202234
 92593516 72350290 20243226
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
189 363 155 6
26 67 2 2
27 92 3 4
21 124 7 7
24 110 150 74
44 163 10 9
256 180 45 28
1514 176 37 23
26102 246 89 38
236884 275 396 119
748009 311 2693 575
1719318 423 4090 1554
3084770 565 5262 2907
4328081 889 7496 5287
4692192 1616 10369 8364
4497114 2922 15311 13520
3745349 5105 21018 20041
2756136 8156 29014 28744
1755170 13133 39736 39502
874502 19853 53465 53609
330831 28928 68872 68655
127799 41733 85274 85582
104315 59599 103019 103343
119321 82505 123563 123740
140493 110014 145300 145338
165769 141055 171242 171382
193140 173319 197905 199773
220992 206432 228222 227812
250137 236940 256188 255984
277633 265937 282949 282264
300182 289318 304687 304641
319645 308066 320791 323194
335676 322606 334008 335452
340015 332811 345013 344689
345671 341150 352049 352009
349603 347880 356534 356953
354871 353568 359660 360298
360691 357005 365930 366459
364150 363976 370532 370999
371905 371299 377407 377176
379553 378472 384920 385689
388866 388984 395339 395607
401684 403026 406417 407869
415903 415724 419614 420193
430786 431326 434459 435045
447024 445928 450270 450390
461691 460926 462464 462474
471942 471263 473994 474232
478422 479011 479831 480838
482141 481086 481620 481715
477565 477186 479334 479116
468203 468407 469420 470163
453911 453708 453114 454833
433641 434017 434472 435012
411009 409988 409953 410053
384768 385198 382899 383641
356153 357298 355914 356249
327845 328925 327752 327929
300483 302267 300282 300364
276923 277486 276294 277063
256469 257515 256502 256613
241069 241112 240435 241428
230800 230371 231175 231107
223085 223962 222870 224040
226377 226617 227385 228144
239472 238872 239174 239470
257814 257702 256855 258258
280586 279193 279651 280927
312627 311707 311579 312897
350521 349692 349103 349577
396342 396175 396293 396837
422448 422123 422577 423399
448296 447876 447825 448785
462876 463171 461735 463047
454781 456554 454899 456256
410540 411911 410674 412149
344462 343603 343539 344717
242322 241368 241136 241473
127605 128426 128510 127492
48085 47862 47783 48024
7687 7916 7782 7794
59 60 55 70
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
