A = [
3931202 4004641 23259464 1862000 1803087 1655485 1410438 1371641 1302264 1324231 1451244 1600715 1801509 2010278 2208245 2351453 2360090 2382828 2387045 2266210 2217278 2229880 2192152 2177080 2211388 2557839 2632375 2613160 2864032 2486382 2475317 2412521 1980411 1995077 2004507 1997870 1982003 1941127 1941449 1951795 1948841 1944529 1960544 1974396 1968414 1951814 1953622 1963977 1928656 1941732 1953839 1922659 1960904 1977013 1955680 1946845 1935327 1933596 1890788 1843708 1860256 1847290 1839846 1836342 1832522 1839045 1804090 1835380 1855599 1848718 1906715 1959815 1982725 2005095 2034141 2036130 2037553 2036606 2005097 1983107 1965023 1952204 1936995 1924617 1926284 1904855 1884992 1837760 1805105 1789170 1768962 1754410 1748385 1740721 1735655 1732029 1722383 1714178 1697643 1673058 1664313 1650857 1637394 1634105 1627894 1625305 1617776 1610870 1599857 1586193 1568488 1557404 1548198 1542195 1534187 1534555 1529345 1524893 1513078 1499975 1487935 1473849 1460812 1451499 1445717 1437817 1433431 1428371 1415984 1402761 1390797 1376815 1362166 1352521 1349389 1340219 1334546 1331125 1319721 1306075 1297064 1284922 1272655 1262791 1250317 1241707 1239237 1230077 1221855 1216878 1203273 1191502 1182432 1164477 1156295 1146672 1140045 1131376 1123102 1114881 1105043 1095790 1082422 1070862 1059110 1050866 1044491 1036660 1029157 1021760 1011637 1004579 991447 982307 970822 961927 953859 948623 938183 932772 923238 915170 906446 893924 885250 877814 867968 860953 853781 848613 841668 832722 825525 815824 806187 798364 788774 780367 774147 768137 764087 756638 745673 737974 728185 721673 715999 705883 699695 692407 684954 676575 671022 661182 655241 645848 639081 631379 625856 617801 612980 605996 598764 590736 581859 574133 565712 556774 549072 541188 536505 529112 522804 516032 509400 500668 494017 486714 480105 475338 468986 463244 456909 450185 446841 439386 433447 426987 420685 415222 411761 406393 401446 394955 391451 385823 377695 372816 369041 363856 356587 354295 348970 344239 340122 334627 330206 324944 320701 315948 311849 307326 303710 300295 296811 291560 286474 282681 278514 274286 272205 266636 263223 259372 256320 253136 249133 245835 242221 238599 235125 231697 228357 225211 223228 218712 217270 213519 209883 206910 203879 200646 197707 195323 192222 189495 186634 183448 180528 178568 176174 173247 170406 168447 165793 162508 161350 158392 156391 154807 151726 148109 146807 144689 142048 140250 138498 136447 134394 133431 130644 128663 126860 124752 122875 120440 119540 117352 116297 114016 112667 111165 108842 107500 105734 104005 102969 101559 100602 98473 96905 95541 94174 93484 91387 89617 88757 87565 85919 84725 83295 82705 81162 79555 78969 77313 75626 75389 73836 72549 71993 70677 69767 68929 67433 66717 65314 64606 63494 62499 62097 60325 59587 58875 58095 57243 56086 55241 54206 54039 52805 51475 51005 50702 50030 49146 48351 47455 46686 45602 45096 44997 44118 43167 42699 42309 41404 40425 40006 39393 38704 38216 37868 37283 36593 35809 35110 34914 34174 33736 32973 32876 32623 31882 31344 30939 30594 30289 29636 28850 28588 28514 27990 27221 26737 26604 26166 25830 25368 24849 24613 24378 23940 23513 23551 23049 22559 22068 22098 21172 20712 20885 20594 20171 19711 19504 19256 19026 18591 18655 17984 17928 17414 16949 17040 16957 16540 16299 16287 15803 15631 15384 15218 14898 14552 14465 14093 14054 13968 13544 13340 13017 12927 12882 12644 12387 12307 12228 11972 11623 11603 11325 11012 11025 10864 10766 10680 10292 10033 9937 9783 9617 9587 9472 9285 9201 9037 8967 8763 8607 8536 8394 8190 8071 7847 7785 7790 7712 7511 7428 7378 7208 6959 7025 7003 6707 6691 6565 6507 6330 6267 6189 6088 5830 5912 5818 5734 5850 5564 5543 5343 5278 5310 5145 4973 5382 4924 4837 5010 4811 4647 4660 4643 4580 4419 4323 4418 4263 4231 4098 4057 4073 3886 3897 3963 3807 3729 3676 3771 3654 3590 3557 3451 3439 3420 3350 3394 3329 3245 3234 3104 3093 2987 2995 3027 2853 2896 2918 2806 2822 2805 2820 2557 2724 2503 2528 2567 2552 2437 2386 2465 2393 2257 2310 2257 2245 2247 2259 2149 2133 2144 2135 2080 1965 2057 1967 1994 1951 1846 1895 1775 1853 1748 1901 1816 1649 1743 1675 1675 1648 1604 1676 1631 1510 1566 1567 1567 1476 1459 1480 1515 1392 1399 1386 1394 1411 1364 1354 1244 1333 1300 1303 1261 1245 1226 1240 1144 1216 1186 1157 1213 1141 1129 1139 1033 1085 1078 1067 1049 980 1074 1060 1020 1017 1037 1020 1030 1003 980 933 932 905 868 968 924 912 902 925 849 862 877 840 845 795 775 819 830 843 803 789 788 815 816 770 721 753 771 790 796 765 698 718 679 702 729 737 691 686 692 670 666 666 715 633 643 649 619 661 650 583 613 617 603 635 704 648 560 659 537 617 619 573 574 614 539 567 585 556 581 564 511 553 536 583 559 574 549 509 504 530 437 500 469 461 488 490 513 483 495 451 445 437 451 507 495 454 483 456 454 476 428 418 392 472 454 402 439 394 412 437 421 398 433 422 376 431 399 421 405 429 418 398 375 382 387 425 376 393 417 437 401 378 351 388 380 395 387 349 368 341 320 325 366 323 323 375 301 298 311 337 331 310 292 313 322 353 307 322 316 299 299 319 293 324 274 318 325 307 284 286 277 288 282 302 298 301 317 288 312 296 297 277 294 299 283 271 237 252 279 289 306 280 254 261 281 281 268 279 254 251 270 258 259 267 270 233 229 271 263 247 259 274 230 264 248 241 243 245 231 245 246 245 213 224 248 251 217 232 212 247 218 247 205 220 224 198 205 229 219 218 212 233 223 239 226 216 215 223 223 219 207 205 203 212 222 220 215 178 201 223 180 206 238 177 212 194 191 186 186 210 214 185 178 157 192 198 264 190 176 173 189 174 175 172 152 178 169 174 169 162 193 186 177 178 175 163 156 143 170 185 183 147 155 159 170 179 158 147 139 151 148 176 142 157 152 150 179 123 129 152 155 155 157 149 122 161 159 147 155 143 143 157 151 155 145 161 166 159 191 220 174 170 187 168 222 162 319 412 376 304 304 292 381 325 203 358 341 330 321 242 218 163 160 153 132 154 135 116 143 154 128 128 137 146 146 152 168 170 102 137 144 130 123 103 117 117 99 160 105 123 111 119 124 112 100 111 121 112 116 108 98 104 98 119 115 121 114 126 116 106 100 131 100 115 115 112 114 119 109 124 96 98 112 108 124 101 144 118 128 122 127 132 145 123 142 121 131 115 102 115 113 105 101 105 123 127 127 127 119 124 147 149 149 159 129 157 143 152 149 147 148 145 141 135 131 109 120 124 108 97 101 109 101 92 109 99 94 491 102 94 107 117 93 120 116 99 91 110 82 97 102 97 152 94 94 80 111 96 102 67 65 85 88 90 64 90 83 71 91 85 79 78 94 86 85 82 75 98 76 79 71 89 76 78 91 90 92 87 73 89 92 85 72 99 88 93 93 87 83 71 82 87 87 88 89 74 78 78 76 71 80 75 76 89 67 69 96 85 80 83 106 87 79 66 87 105 75 83 56 86 92 75 90 77 80 70 75 60 101 72 92 88 78 102 99 88 93 110 105 127 156 158 112 119 125 145 123 122 94 108 132 113 101 119 138 99 98 133 106 109 100 108 108 78 102 120 87 73 75 74 94 98 82 87 80 117 116 109 70 83 124 78 90 75 84 124 91 95 84 73 189 95 80 77 66 134 75 60 50 65 195 60 61 60 61 69 52 51 53 48 34 51 49 28 49 44 60 40 45 46 53 51 51 37 40 53 50 39 35 44 47 43 33 52 42 39 52 48 49 51 42 51 47 47 60 54 42 60 52 47 30 47 49 47 41 53 49 48 45 43 41 45 50 46 43 40 46 39 53 26 40 43 46 45 40 43 47 43 37 31 38 28 42 33 41 36 45 59 40 40 49 47 43 47 48 53 46 48 49 61 58 54 52 38 42 40 47 31 34 38 41 45 43 40 45 42 38 35 46 57 52 47 44 51 32 32 23 35 44 41 54 34 41 43 36 55 52 36 35 29 43 30 39 30 58 52 44 44 40 50 44 34 40 36 50 43 39 43 36 43 59 37 45 42 37 36 41 37 40 50 50 31 30 27 45 46 46 38 43 51 45 37 39 37 51 37 31 36 36 33 24 44 36 44 50 54 58 58 70 61 67 55 52 60 64 40 44 43 56 36 43 48 47 46 61 41 52 50 51 44 36 39 57 50 48 49 38 54 49 54 31 40 44 51 63 43 54 61 66 50 42 47 51 84 56 35 56 60 35 51 36 57 37 49 32 36 44 51 64 65 39 76 48 45 46 48 51 49 46 52 34 42 57 56 64 58 68 54 64 61 82 26 43 29 52 48 35 39 66 41 26 42 38 31 29 31 28 33 32 36 27 29 35 17 20 22 18 17 17 18 22 31 18 22 17 29 17 17 23 19 22 20 17 21 23 16 31 27 15 25 27 28 25 28 10 15 31 27 23 28 23 32 32 23 19 35 24 30 21 23 23 27 24 20 25 38 22 20 18 32 37 36 23 20 20 33 40 32 26 25 24 44 21 20 33 34 27 21 30 30 27 17 23 21 24 17 24 18 16 15 17 15 12 22 20 14 12 17 20 17 9 22 13 12 7 14 9 9 12 10 16 14 8 10 14 12 10 15 14 16 15 13 8 13 10 8 7 12 14 23 13 10 9 13 15 8 12 3 11 14 8 12 8 10 7 12 8 12 17 14 12 11 15 8 15 9 9 18 14 8 12 14 17 13 14 16 17 16 17 11 10 14 14 12 8 12 10 9 7 11 13 12 6 13 13 6 8 13 13 13 11 16 15 11 9 9 11 7 11 13 7 13 9 8 27 7 10 9 17 14 8 18 14 12 6 11 15 13 9 11 7 12 15 12 4 12 11 20 9 13 11 7 13 15 9 14 14 8 6 5 10 12 13 11 13 14 9 6 8 13 13 15 13 6 14 12 9 8 6 11 10 15 12 10 12 15 16 16 8 10 15 9 20 9 14 8 20 11 12 13 9 3 14 7 18 15 17 13 8 15 8 9 17 12 8 12 9 10 17 12 7 12 5 17 14 12 11 11 9 14 11 16 9 12 11 2 10 16 13 11 9 17 10 12 1 7 10 9 9 6 10 5 16 6 11 16 8 10 8 10 6 11 7 7 9 6 14 11 11 11 14 12 8 11 5 11 5 7 7 5 8 8 18 9 20 9 13 19 10 10 
];
B = [
0 0 0
 950348 630988 319360
 1207407 826404 381003
 799421 552420 247001
 2309394 1647856 661538
 1067147 781565 285582
 772202 576173 196029
 844421 635342 209079
 604225 460069 144156
 472794 365958 106836
 403914 311242 92672
 591591 454006 137585
 591407 454026 137381
 468665 360954 107711
 2073202 1597200 476002
 811563 633918 177645
 944929 747257 197672
 741415 595969 145446
 958136 756784 201352
 991292 787189 204103
 750984 599798 151186
 1797694 1419047 378647
 1114023 889955 224068
 1127149 903422 223727
 789497 639133 150364
 1130799 910796 220003
 1073272 864888 208384
 1609050 1287688 321362
 822429 660632 161797
 1184932 953233 231699
 1203414 971476 231938
 841690 687259 154431
 1247511 1009613 237898
 1155561 926651 228910
 1575349 1275732 299617
 871382 712580 158802
 1231738 995164 236574
 2036435 1674532 361903
 1173070 950938 222132
 997727 820643 177084
 1839246 1513234 326012
 1438966 1165701 273265
 1740327 1431205 309122
 838699 687822 150877
 1319611 1077533 242078
 1762926 1451037 311889
 971076 800653 170423
 1726998 1421370 305628
 1334961 1086991 247970
 1699287 1396265 303022
 947897 781221 166676
 1669657 1372055 297602
 1353479 1100630 252849
 1698279 1390377 307902
 877361 726631 150730
 1792356 1472451 319905
 1579491 1296286 283205
 822837 677947 144890
 1612169 1319646 292523
 1080329 871667 208662
 141242708 119068264 22174444
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
108 919 6 11
17 84 1 1
34 248 3 5
64 159 2 9
62 162 10 14
90 163 28 42
741 237 61 104
8871 263 135 238
90243 280 188 343
296280 415 436 614
466531 548 4535 1428
744462 791 6955 2853
1139524 1193 8834 4311
1903358 2223 11080 6282
3420080 3915 13598 9214
5861437 6937 17146 13455
7408767 11446 24752 21954
6419916 18010 38013 35718
4025654 28745 57024 56592
1940882 43090 82358 81550
737775 62567 109108 109399
278967 90035 136266 136780
186873 125838 165653 166227
202012 167987 197590 198805
235453 215523 234096 233595
276447 264653 273860 275551
321884 314718 318203 319935
370929 365420 367636 368173
421913 417515 417617 420347
472958 469887 470129 471743
524121 521682 521392 523546
571120 567664 568407 571085
610304 611168 610712 613911
646278 648709 645253 647744
675604 676126 672430 676514
693730 696123 694833 696921
711500 714845 711370 713275
722668 726416 723239 727669
735671 736943 733545 737782
746249 751737 747566 748172
761622 763276 761352 763286
781803 781806 779407 784007
804791 807597 803585 807475
834236 835550 832165 836540
866286 867825 866330 869045
902072 905165 903363 905554
940733 940940 938962 942268
972037 973302 971160 975218
998875 997735 996058 1001926
1011703 1012741 1010150 1014296
1010145 1011566 1008450 1012322
988509 992353 990005 994670
953796 957521 953558 958513
905911 911122 905474 910311
845541 850685 847913 850060
775275 780806 778662 779944
705832 710513 708744 711282
640461 643190 640151 642375
579080 581033 578126 579606
526421 528984 527042 530624
490717 491083 490692 491927
463956 464977 463864 467592
444664 444296 443026 444988
442070 440761 440292 442142
452736 453929 451317 454112
476113 477307 474602 478006
507780 507529 507366 507610
559694 561665 556897 558259
596598 596179 595472 598333
621639 622359 620822 624068
628811 628055 626659 629658
615893 614770 614409 617416
563257 562910 563592 565612
472898 473185 472416 473502
383234 382196 381448 384399
300498 299455 299088 300260
221318 221958 220202 221711
156188 156122 156641 157082
118311 118731 117764 118553
85794 85588 86040 85799
58360 57921 58051 58493
36049 35781 35915 35796
3034 3194 3083 3186
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
