A = [
1802329 1778278 9429999 1879467 1914442 1841207 1791596 1915666 1886160 1975104 2160313 2448696 2919882 3376159 3706116 3997476 4390251 4721431 4765054 4726924 4926415 5070343 5014217 4933139 5006463 6105714 6200399 6125960 6981151 5671792 5597945 5427366 4093511 4132784 4083609 4034489 3999270 3885711 3847113 3807809 3749655 3742702 3695994 3663038 3663864 3584768 3533702 3553774 3472790 3419085 3389672 3291397 3276234 3252114 3185353 3120883 3106685 3097054 3011895 2944701 2921633 2874749 2825367 2773496 2731749 2705262 2649629 2602539 2574110 2528144 2501477 2492190 2460568 2441236 2444346 2411075 2382929 2360732 2316610 2275639 2243696 2217195 2172398 2134818 2116797 2067376 2021027 1962404 1922710 1892148 1854410 1816832 1791662 1759701 1731285 1706833 1675626 1652082 1624279 1597566 1572079 1542507 1514730 1489236 1464051 1444269 1419722 1398474 1377651 1356564 1334850 1322276 1303947 1284267 1274393 1255765 1475203 1472706 1459132 1671594 1670768 1648081 1622719 1596507 1569824 1539600 1512541 1484816 1460444 1433876 1405808 1379559 1352615 1327919 1302625 1278386 1253599 1234516 1212547 1188247 1166621 1145189 1122867 1100597 1080973 1059538 1040936 1023765 1002787 980652 962991 944052 928207 907930 891170 874177 854733 837055 823100 805600 791896 776113 761402 748749 731852 716858 703725 691078 679286 666819 654390 642227 630395 616607 607065 595209 583292 573300 561656 551707 540479 531357 522900 512596 503332 495114 483084 477686 467589 460637 453036 444306 436898 430225 422032 411830 405002 397795 391797 383213 377754 370980 364249 357072 352216 345588 338494 333192 327242 321455 314916 308431 302679 297886 293994 288924 284182 278936 275068 270153 265733 262344 257292 251959 246195 240753 234673 229288 225291 218617 212517 208721 205622 201041 196583 194340 189882 185610 182422 179135 175868 173020 170669 167362 163571 161915 158536 155374 152846 150191 147011 144178 141503 138571 137097 134840 132674 129665 126611 125532 123377 121124 119234 116581 114539 112469 110105 108817 106843 104918 103102 101665 99695 98243 95316 94104 92348 90911 89177 88303 86177 85094 83462 81884 80982 79234 77507 76623 74856 74151 72412 71986 70331 68757 68221 66852 65487 64861 63510 62181 60492 59977 58763 57528 57048 55896 54997 54382 53291 52173 51427 50639 49709 49268 47931 47071 46212 45473 44658 43894 43081 42716 42014 41230 40523 39958 38863 38225 38000 36878 36695 35724 35217 34657 33624 33493 32711 32377 31918 31421 31193 30388 29999 29440 29073 28061 27839 28072 26851 26443 26080 25449 25078 25045 24634 24176 24029 23526 22985 22248 22252 21963 21595 21133 20858 20557 20310 19753 19585 19205 18881 18679 18272 18055 17609 17469 17143 17025 16628 16289 16082 15566 15440 15287 15036 14751 14738 14384 13984 13778 13908 13471 13306 13025 13004 12509 12269 12205 12023 11864 11598 11597 11271 11280 10762 10813 10785 10379 10049 10198 9906 9639 9604 9597 9472 9189 9133 8955 8856 8779 8644 8308 8301 8113 7914 7981 7817 7680 7531 7312 7250 7203 7119 7110 6945 6708 6635 6608 6398 6395 6472 6231 6273 6082 5897 5766 5748 5672 5494 5562 5428 5334 5401 5264 5194 4987 4825 4925 4861 4588 4747 4633 4497 4420 4361 4219 4264 4320 4122 4118 4033 3961 3999 3898 3806 3786 3732 3659 3594 3461 3390 3447 3343 3341 3241 3268 3285 3122 3059 3073 3033 3010 2999 2953 2940 2687 2775 2677 2703 2652 2705 2543 2590 2523 2514 2522 2399 2373 2349 2279 2290 2316 2182 2274 2162 2232 2145 2039 2003 1991 1965 1914 1987 1951 1872 1814 1848 1876 1740 1808 1758 1718 1766 1714 1574 1647 1627 1560 1580 1599 1553 1571 1519 1523 1466 1448 1469 1420 1435 1400 1436 1430 1299 1230 1297 1214 1324 1257 1240 1241 1193 1135 1199 1141 1145 1204 1117 1097 1161 1144 1059 1071 1025 1043 1048 1004 1021 931 975 922 936 957 940 924 917 925 908 886 874 862 858 853 807 785 792 825 818 772 798 730 797 799 772 753 771 763 742 695 715 765 710 684 637 693 691 622 662 661 663 607 654 635 587 590 612 601 601 636 556 563 563 539 514 513 532 535 502 491 523 532 537 515 500 460 456 467 469 430 468 476 453 437 468 477 424 450 433 438 417 405 376 424 393 390 430 417 412 395 393 373 395 373 407 394 369 355 365 356 323 358 338 357 362 340 288 364 346 332 343 328 331 306 322 314 324 324 324 302 305 297 308 304 289 284 319 328 298 318 296 296 279 300 316 278 323 290 281 252 294 249 248 281 260 264 263 304 237 249 281 263 266 257 258 255 255 234 248 252 260 239 251 204 244 214 211 220 214 215 224 252 213 220 205 202 195 210 208 217 169 204 214 191 216 206 206 190 184 185 187 188 188 202 201 196 178 199 173 172 177 166 180 182 181 165 175 163 185 187 164 142 152 165 154 164 160 169 163 165 167 150 176 134 164 154 137 148 135 160 151 141 152 149 138 142 187 146 151 144 127 147 137 142 139 137 148 147 125 131 109 134 121 130 145 137 121 151 137 125 144 132 116 117 125 127 101 126 109 102 128 130 118 126 116 112 112 104 127 116 124 123 113 114 110 141 101 107 112 127 116 100 130 116 102 100 107 93 106 93 105 80 96 94 121 95 96 103 110 103 89 111 90 102 96 87 97 94 92 93 78 78 84 99 84 86 93 82 87 89 98 84 115 88 84 82 77 100 69 74 74 73 77 79 86 94 98 70 80 83 80 88 90 84 80 71 82 66 59 73 81 76 77 78 72 61 63 66 71 79 71 74 61 58 73 68 67 57 75 66 79 51 73 58 68 70 77 64 61 69 56 66 65 57 65 54 54 64 67 67 57 54 53 55 59 56 53 55 59 58 58 63 57 58 51 56 60 69 60 48 39 45 63 52 49 45 51 53 61 63 59 58 56 59 39 49 38 44 44 61 47 42 53 40 57 58 42 52 40 56 53 41 43 39 63 56 34 43 56 50 35 45 36 49 40 40 48 46 43 40 38 35 38 34 47 46 44 35 33 48 47 43 41 45 49 42 49 39 47 44 45 53 50 35 49 52 49 48 44 51 52 60 50 45 42 54 52 72 66 60 61 55 57 61 55 63 59 54 52 53 47 55 53 53 52 51 42 49 36 41 46 38 38 37 44 51 58 361 55 57 51 55 45 48 42 19 39 39 39 27 43 41 40 35 37 52 37 34 37 31 46 39 38 29 44 36 30 38 34 31 31 35 36 38 30 40 29 27 31 28 40 34 27 40 36 37 24 27 22 30 33 38 14 23 32 31 26 38 32 36 24 44 38 36 55 72 382 23 22 23 19 27 24 19 24 28 14 13 20 28 18 19 16 24 22 21 13 25 19 11 17 19 16 18 22 23 15 20 30 24 17 26 26 26 14 19 21 32 24 26 20 16 18 22 15 25 24 28 16 11 17 27 21 27 22 18 25 28 14 23 18 20 19 22 30 17 27 32 27 19 14 32 25 21 28 26 25 14 21 23 20 24 18 16 24 34 28 34 27 32 25 28 22 26 29 27 31 29 25 31 37 25 19 22 24 24 25 23 20 33 20 25 40 25 18 29 23 28 27 34 34 32 35 29 19 26 29 16 18 25 14 18 22 22 28 23 18 23 23 14 16 18 8 16 16 22 12 15 5 13 9 7 10 10 17 5 19 12 8 21 9 13 14 15 14 17 13 14 13 20 17 17 17 11 10 11 20 14 11 7 18 10 18 14 13 18 10 16 13 12 11 10 17 15 18 8 13 8 12 10 8 18 14 14 11 4 15 14 15 10 11 14 10 8 14 10 15 15 5 11 11 10 10 13 10 11 8 10 8 9 9 11 9 14 17 12 18 12 8 12 9 14 15 13 10 8 11 9 13 12 7 8 12 9 6 6 5 13 8 4 14 22 11 3 8 12 8 7 9 10 7 7 10 10 12 9 11 7 9 13 9 10 6 7 8 1 11 7 11 11 5 11 5 6 8 7 8 6 10 8 9 10 6 4 9 9 5 10 8 8 12 9 4 7 9 6 9 9 6 14 5 6 5 8 10 10 6 6 11 10 13 3 7 7 10 11 10 10 12 7 9 8 8 6 8 6 13 5 4 8 14 7 9 7 11 9 8 6 10 5 7 17 4 5 10 7 8 8 10 9 5 8 10 10 8 11 6 16 5 7 13 6 8 9 10 6 6 15 9 12 10 9 8 8 12 11 8 9 4 8 8 8 10 13 12 11 3 9 5 2 7 6 7 9 7 9 6 4 9 7 8 8 6 6 5 7 11 5 5 9 7 6 10 6 4 4 2 5 8 5 8 2 9 4 9 8 2 3 2 9 6 3 4 5 9 4 4 2 4 6 4 2 1 5 5 5 3 5 8 12 9 2 4 4 6 4 4 9 5 6 4 5 2 4 6 3 5 6 3 4 2 8 4 6 6 4 5 5 3 3 1 2 4 3 3 5 3 3 6 9 3 3 3 5 5 4 6 0 5 6 2 3 0 1 3 2 4 3 1 1 3 1 7 4 3 2 3 0 1 4 4 3 2 1 1 1 5 2 4 7 1 3 0 1 3 2 4 3 3 4 1 5 3 1 5 0 2 4 2 2 2 2 2 3 7 4 2 0 1 6 4 7 3 2 5 3 2 5 3 1 3 4 4 4 3 3 5 3 6 4 3 2 3 0 2 4 2 1 3 3 3 3 0 1 2 4 1 3 2 2 3 2 2 0 1 6 2 2 4 0 3 2 2 3 2 6 4 1 1 1 0 2 0 7 2 1 4 0 4 2 5 2 0 4 3 4 3 4 3 2 0 2 1 1 1 3 1 3 0 2 1 1 1 0 2 2 1 0 2 3 1 2 4 1 1 1 1 3 0 0 1 2 2 0 3 3 2 1 0 2 2 0 2 1 3 1 0 3 0 2 1 0 1 3 0 2 4 1 1 5 3 2 1 4 5 4 4 5 4 1 1 3 1 0 1 1 4 1 3 1 5 4 3 2 2 1 0 1 4 0 1 2 2 1 2 4 1 2 1 3 4 1 1 1 2 2 2 0 0 1 1 3 2 0 2 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 3 1 0 1 0 1 1 2 0 0 3 1 1 0 0 0 1 2 1 
];
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
 1339615 1060774 278841
 1386364 1106407 279957
 3037571 2437500 600071
 1395468 1119039 276429
 3587402 2901692 685710
 1558055 1256484 301571
 1524384 1230527 293857
 6717300 5515721 1201579
 1879626 1534523 345103
 2605003 2145712 459291
 6304428 5191842 1112586
 2618295 2158967 459328
 3687715 3046985 640730
 4111301 3385683 725618
 2140596 1767975 372621
 3165251 2615193 550058
 4574924 3790540 784384
 2992930 2478396 514534
 1311738 1073693 238045
 8261266 6910224 1351042
 1309683 1075236 234447
 2557824 2124427 433397
 10490378 8845581 1644797
 2396709 1996412 400297
 1038895 855205 183690
 16608872 14120138 2488734
 1521929 1268327 253602
 959589 792757 166832
 1523139 1274034 249105
 748823 617258 131565
 119745153 109262415 10482738
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
8 58 0 0
3 5 0 0
3 18 0 0
7 32 0 0
8 18 0 0
9 25 325 11
573 42 936 78
5810 38 1171 249
299033 61 1557 476
2648406 84 2237 901
5219277 118 2638 1393
9024690 200 3608 2336
13059578 348 5323 3827
16393576 709 8485 6573
16372690 1564 12335 10988
13616616 3697 20995 19922
8775313 6925 34699 34181
4797957 11676 51798 51844
2480635 19517 72910 73335
1142983 31046 95204 95303
491542 48614 118918 118893
244169 71242 143441 143574
195381 104402 172653 173337
218828 144724 205685 206749
255642 192913 242070 242443
295590 245457 283069 283032
338008 299081 325097 325063
380566 349752 368400 368573
418319 392906 407070 408286
449717 430223 440056 442270
474892 458341 466934 466749
488350 477313 483013 484538
497301 488604 492262 494391
500503 495913 497758 499996
503587 499139 499681 501215
505543 502232 502672 504843
504865 503302 505294 504899
509681 508536 508204 508553
514435 514099 512791 514200
519753 519140 518979 519685
527855 527739 528488 529054
541048 540556 539943 541122
556257 556203 555828 557418
577468 576486 576008 576309
600071 601581 599725 601718
628058 627787 625608 627381
654109 653620 654272 654279
678105 678463 676556 677738
699340 700218 699338 700390
716956 718650 715810 717981
727275 728583 728411 728437
728708 730975 728488 730307
721141 722118 720730 720705
707502 711056 708200 708526
683849 684939 682932 685108
653883 655851 653423 655200
615450 616370 615931 617906
571046 573374 571719 572925
520617 520860 520048 521022
472655 473502 472231 474971
426902 425966 426931 427058
387089 389867 388045 389310
348181 346830 347515 348150
320825 319520 320456 320457
301191 301475 301483 302238
290874 290172 289124 290636
287218 288553 287707 290885
284953 285342 283984 285237
274883 274155 273048 274818
278858 278374 278994 279128
270762 271565 270517 270908
255442 254173 254667 254620
239440 239775 239334 239051
205604 206010 205049 205939
173741 173843 173933 174003
141361 141067 141161 141307
104843 105619 105105 105154
67755 67463 67142 67653
51783 51139 51133 51696
37259 37421 37228 37256
20876 21096 21005 20783
9965 9778 9844 9748
443 454 427 450
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
