A = [
2164227 2062682 4437264 2239647 2176823 2137460 2067128 2217119 2246253 2339984 2564565 2863259 3327576 3770124 4207827 4523654 4900279 5329367 5373973 5291523 5421281 5472266 5378932 5286231 5297709 6033078 6043889 6006076 6589798 5308823 5267311 5156201 3931375 3956353 3913687 3883511 3858012 3752208 3732282 3708058 3663623 3671200 3640381 3633218 3647513 3579351 3542019 3574793 3497758 3452019 3440696 3336463 3343465 3323106 3260845 3205718 3201593 3211410 3111751 3044284 3044813 2982327 2940842 2898898 2863487 2859238 2802975 2749632 2731858 2680416 2658273 2651291 2615215 2603598 2610727 2579815 2557626 2535309 2489456 2445702 2416538 2388948 2338072 2303438 2294512 2247763 2202533 2137031 2091713 2065414 2029015 1995363 1972340 1940212 1915819 1893386 1869509 1849764 1827454 1797088 1775716 1747620 1721036 1699359 1677796 1659735 1643112 1620363 1602014 1582918 1562369 1556018 1536457 1516534 1507996 1493786 1740251 1740599 1726883 1968238 1970283 1954276 1931747 1908659 1886608 1866438 1842260 1824111 1801813 1781875 1759826 1730131 1707089 1682707 1662765 1639982 1616891 1603349 1585549 1563509 1544414 1523689 1504580 1482557 1459961 1438165 1423369 1402315 1385553 1370556 1349351 1330441 1312197 1292696 1273577 1256548 1234513 1221466 1206958 1188835 1173857 1159278 1143444 1126667 1107845 1093515 1077242 1064049 1050620 1036185 1025453 1009950 995257 983640 969686 954486 941893 929072 918009 904924 893911 883105 872915 859645 849464 838375 824596 814342 802334 798267 784602 772576 763585 754304 743437 733693 721223 712799 702673 693220 684309 676742 668712 658208 648441 641217 631904 622560 613571 603022 595175 586281 578653 570672 563669 555746 548104 540155 534296 528080 519130 510584 505575 497846 490431 480584 473512 463366 454761 447477 441104 434754 426730 420725 413932 407519 401588 396402 390463 384388 377943 372804 366694 362363 356408 351124 345164 339810 334867 330700 325090 321016 315361 310509 307621 302455 296244 293400 287859 282832 279753 275378 271029 266588 262418 259627 254790 251362 247061 243321 239836 236539 233556 230068 226080 222411 219425 215923 212324 209982 206627 203112 199727 196980 193660 191889 188203 185550 183315 179351 177031 173911 171360 169799 167075 164717 161507 159612 157131 153871 151957 149853 147684 145334 143013 140664 138485 136896 134287 132929 130654 128521 126836 124834 122799 120568 118148 116742 115535 113964 111484 110296 108618 106928 104426 103349 101420 100846 99145 97439 95796 94442 93370 91254 90171 88462 87478 85742 84263 83011 82533 80907 80322 78386 77573 76268 74859 74436 72224 71787 70463 69181 68549 66684 66214 64981 64299 63295 62596 61038 60463 59404 58295 57538 56694 56062 54898 54049 53430 52282 51942 50955 50303 49262 47983 47902 47212 46228 45317 44601 44464 43418 42767 41875 41678 41042 39999 39606 39337 37860 37815 37100 36904 35915 35336 35357 34381 34002 33682 32963 32090 31958 31337 31018 30318 30311 29275 29190 28667 28235 27360 27190 26738 26344 26296 25827 25437 24970 24551 24096 23740 23412 23036 22790 22234 22028 21558 21278 21150 20697 20091 19966 19756 19541 19196 18927 18490 18151 17898 17712 17560 17257 16618 16716 16303 15808 15790 15638 15208 15344 14816 14655 14523 14421 13961 13783 13551 13409 13212 12776 12648 12701 12206 12326 12143 11919 11561 11455 11373 11189 10957 10779 10745 10591 10389 9985 9880 9877 9763 9562 9475 9323 9107 8852 8817 8743 8679 8409 8257 7932 8136 7907 7857 7914 7581 7495 7293 7242 7238 7047 6860 6977 6819 6442 6646 6451 6392 6236 6244 6094 5874 5774 5814 5623 5527 5499 5528 5360 5385 5259 5186 4977 5075 4941 4885 4735 4671 4615 4628 4565 4460 4324 4375 4262 4252 4099 4020 4074 3917 3856 3822 3818 3720 3688 3648 3527 3524 3570 3407 3458 3379 3341 3173 3095 3043 3130 3148 2998 2929 2930 2914 2833 2802 2762 2758 2635 2709 2608 2548 2577 2469 2488 2435 2425 2398 2289 2292 2383 2220 2340 2199 2193 2199 2074 2109 1986 2012 2017 1925 1977 1928 1874 1902 1887 1843 1784 1780 1729 1663 1713 1634 1687 1666 1613 1653 1564 1593 1551 1512 1453 1507 1502 1532 1482 1416 1461 1380 1343 1404 1344 1349 1253 1332 1237 1250 1252 1215 1202 1156 1077 1208 1161 1123 1110 1089 1058 1083 1056 1076 1011 1014 1050 998 1024 1011 1032 913 984 969 904 928 903 892 909 915 884 867 821 865 814 818 870 801 814 801 813 779 797 773 756 761 688 688 753 730 721 771 674 717 640 685 740 663 646 674 653 647 620 641 594 589 566 649 613 597 617 629 587 568 632 558 595 617 563 544 595 567 520 532 560 511 490 560 550 511 491 546 507 517 459 485 529 468 509 476 453 468 480 446 467 486 452 450 430 414 403 453 425 394 444 445 421 412 393 441 426 434 415 395 398 405 396 401 369 397 365 384 366 331 384 321 360 357 314 325 290 322 337 348 342 325 330 329 321 308 338 312 321 307 344 330 304 319 298 303 336 292 323 276 301 299 294 289 324 277 294 281 263 293 272 285 287 256 251 286 238 264 264 256 261 253 254 249 291 233 261 274 246 242 279 262 280 249 233 235 262 270 228 219 242 251 246 221 219 212 214 242 220 214 233 215 209 220 204 216 205 213 238 238 241 237 216 198 205 212 217 212 183 159 203 195 210 208 204 176 189 193 190 172 175 183 207 167 186 179 180 179 204 180 160 165 177 196 166 167 177 163 176 174 155 188 164 164 149 147 163 153 169 175 176 179 150 139 154 136 129 147 133 150 155 145 130 155 160 142 152 133 159 140 147 153 155 150 126 133 137 143 123 133 137 138 142 126 129 137 131 120 149 126 138 127 121 141 121 130 119 118 121 123 120 123 123 107 116 118 121 121 108 129 129 124 126 109 96 110 129 132 102 99 107 97 111 159 116 109 93 126 111 127 117 121 96 108 103 124 112 100 105 91 102 90 95 125 112 99 77 115 115 104 100 108 98 94 114 97 92 91 84 100 100 107 82 85 83 109 91 70 102 71 88 108 103 102 92 92 98 84 88 83 103 91 95 93 81 76 73 83 97 79 109 72 84 69 84 84 87 78 82 72 94 101 93 82 78 107 80 78 98 110 110 111 89 101 121 116 85 80 88 85 86 95 89 112 100 96 102 92 112 97 95 106 95 107 120 105 95 114 110 105 105 109 117 98 116 114 103 98 99 94 101 85 106 101 100 81 88 96 88 83 98 79 87 91 103 102 479 124 103 85 113 97 85 102 67 83 76 94 71 57 80 77 63 93 60 70 85 66 63 68 78 68 46 59 66 67 65 70 66 56 53 59 74 73 76 78 89 130 80 82 55 64 66 73 51 66 46 50 63 58 54 44 62 52 69 61 49 75 68 61 64 63 80 78 114 768 38 42 48 42 37 41 45 48 53 41 48 35 43 44 35 33 43 37 46 39 51 52 35 42 48 43 39 40 38 43 36 30 41 30 39 41 45 40 38 41 44 31 32 36 37 45 40 40 51 37 39 46 51 34 54 27 33 41 37 53 33 39 41 45 38 43 47 54 40 48 46 45 57 47 54 63 62 71 40 58 45 58 51 54 70 51 72 64 54 52 61 46 62 53 59 53 75 58 63 56 55 62 65 68 70 57 64 69 58 54 68 58 53 66 64 65 68 60 83 63 71 69 60 71 60 69 77 75 76 56 69 52 54 51 54 68 52 55 50 54 37 38 31 47 38 35 28 34 41 17 25 39 26 33 22 25 25 29 26 29 19 20 29 25 24 21 31 26 22 23 28 26 23 15 22 25 14 22 35 20 15 14 17 21 17 22 23 24 24 30 24 22 28 26 26 28 28 29 17 18 24 23 24 26 22 30 20 32 23 25 23 25 24 30 24 30 19 26 18 30 28 26 41 26 32 23 24 27 17 18 16 16 22 20 25 22 19 24 21 18 23 16 17 31 16 12 13 22 12 22 25 29 22 27 18 15 14 16 19 14 23 19 16 17 20 21 18 16 20 23 24 19 18 17 18 18 13 16 26 17 15 16 11 10 19 21 13 20 29 13 12 20 10 18 11 19 13 19 12 13 11 19 11 16 20 16 25 12 15 7 15 13 17 6 12 13 7 15 16 12 8 13 13 9 9 12 14 12 11 16 16 18 15 16 16 11 17 20 20 14 17 12 16 17 15 18 14 8 18 16 20 18 13 16 9 14 10 21 10 20 16 13 10 15 9 8 16 14 16 8 11 17 14 21 12 16 6 14 12 16 11 9 10 20 20 10 10 12 12 14 6 9 14 7 10 8 16 18 12 15 15 13 9 15 11 18 11 14 14 10 12 14 15 7 15 8 7 10 9 12 13 7 8 10 7 10 10 8 7 24 8 12 11 10 8 8 7 7 12 9 4 8 8 5 8 6 6 6 6 15 5 8 15 8 8 10 5 12 7 5 6 8 10 3 9 9 14 8 6 6 8 8 14 9 7 11 10 5 7 7 5 3 8 8 8 8 7 8 8 6 5 4 8 7 12 5 4 6 7 10 5 7 5 1 1 6 7 3 5 4 8 7 4 5 1 3 7 7 7 5 7 3 7 1 4 2 7 7 3 5 1 3 6 4 3 5 4 5 4 6 5 5 5 4 6 5 8 3 4 4 6 7 2 6 7 2 5 2 5 4 4 4 3 4 3 3 3 4 2 7 3 1 5 4 4 3 3 4 4 4 3 4 1 2 1 8 3 2 3 4 1 2 0 5 1 5 4 2 1 3 4 8 5 5 3 7 3 4 3 2 0 4 2 2 5 2 6 1 1 6 3 2 1 3 2 2 5 5 2 3 4 7 5 5 4 3 1 7 6 1 5 3 2 3 1 3 2 4 4 2 4 3 4 7 0 3 4 2 7 4 5 7 2 3 0 2 2 3 4 3 4 1 2 0 6 5 3 3 4 3 2 2 3 0 2 1 6 2 4 1 3 2 0 7 2 1 4 2 1 5 1 2 4 2 5 3 2 5 0 2 7 2 3 3 2 1 4 6 5 1 5 1 3 4 2 5 3 5 2 2 5 2 1 4 2 3 3 4 2 2 2 0 6 2 2 1 3 2 3 5 4 4 0 1 1 1 2 6 1 3 2 0 2 2 2 3 2 1 2 1 4 3 4 2 1 3 0 2 1 0 3 1 3 2 0 5 2 2 2 2 3 0 0 4 4 4 1 0 1 5 2 3 0 1 1 3 1 1 1 2 2 1 1 3 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
 1106252 919113 187139
 1114801 924388 190413
 1083492 899397 184095
 1064057 887625 176432
 1333612 1103931 229681
 1087674 909338 178336
 1114313 923562 190751
 2819266 2311873 507393
 1063912 890792 173120
 1320897 1102921 217976
 2426428 2001096 425332
 1273374 1062603 210771
 2198575 1818044 380531
 1080751 909350 171401
 1285993 1077512 208481
 2255853 1874867 380986
 1295524 1089090 206434
 2174902 1804682 370220
 1274519 1073462 201057
 2108095 1757817 350278
 1291831 1092817 199014
 2087285 1743927 343358
 1365326 1152388 212938
 2087500 1746223 341277
 1302543 1102750 199793
 2222744 1864224 358520
 1962776 1647037 315739
 1216143 1032699 183444
 1954408 1641273 313135
 910558 783078 127480
 208020689 188949731 19070958
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
14 53 1 1
5 4 0 0
7 8 1 0
6 8 0 0
7 8 0 2
7 7 2 0
14 15 0 3
418 21 7 1
316144 23 9 1
2109946 33 18 7
3678057 51 44 13
6201873 111 87 46
9495876 186 882 297
13973298 364 3250 1644
17469158 824 5131 3694
19807775 3864 10742 9932
18460217 7154 27916 27058
13782426 15682 51952 51119
8764620 27569 78369 78149
4427193 43020 113957 114541
1751489 61410 141340 141136
588646 86809 171476 172714
265425 124478 197772 198930
235124 168483 227191 227807
250754 222725 256435 257804
276437 280711 291004 291952
307036 342166 327844 328079
341765 398813 369959 371163
379622 450144 411363 413110
415752 495421 449549 453406
447101 533095 484711 486923
469699 558745 510532 512818
489085 581157 530279 533665
502965 591989 540849 544412
513482 593742 549013 552550
513611 587996 546886 549226
508598 574758 539462 541393
509975 563179 535099 536369
510539 556047 532303 531815
512981 549153 527073 529670
514258 542425 524583 528915
517152 541074 528388 529607
527241 544871 534120 538262
539717 553332 545080 548260
558708 570339 562931 565562
583462 592544 587170 589820
616428 623472 618385 621249
648297 654779 650426 653697
687021 692756 687247 691043
725599 730866 726431 729060
759804 765193 761427 764615
787842 790343 786633 790501
802301 804923 802303 806211
808976 814057 808408 812142
802097 806114 801896 805497
778323 781901 779024 782667
740051 744812 741128 745022
691841 694459 691786 693884
635494 636506 634372 636933
572888 574900 572379 575812
516327 517693 517221 519200
461446 462676 462573 464971
408846 410471 410109 411371
363149 363706 362019 364222
333694 334267 334724 334212
317191 317107 316661 317464
314800 314533 312474 314836
297972 298305 296683 298551
287544 287635 286489 288077
288995 288938 288021 288077
279164 279366 278515 279113
265135 264291 264256 265073
243199 242286 242288 242640
213436 213951 212179 214555
184753 183561 183199 184070
150697 150617 150267 150008
109333 108965 109259 109492
76994 77099 77128 77678
60920 61108 60679 60680
41850 41389 41480 41549
22511 22562 22341 22270
9616 9871 9814 9878
503 579 551 469
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
