A = [
1586794 1618756 6932985 1635956 1665077 1570667 1550716 1567005 1561822 1527524 1571960 1664647 1745343 1868437 2060237 2185738 2298452 2453329 2477983 2470537 2498802 2452490 2414283 2407758 2423043 2879129 2901551 2929024 3344846 2942322 2968384 2936955 2558670 2614492 2578054 2574890 2567836 2515109 2507618 2481077 2466048 2457384 2465183 2458283 2454736 2461055 2420735 2403265 2386965 2341763 2326904 2319699 2312673 2305570 2297370 2290400 2281997 2266104 2250519 2234162 2218273 2205657 2193933 2186634 2176512 2162565 2152933 2137875 2124889 2108435 2090529 2077238 2056435 2041958 2029904 2014080 2002599 1986010 1971162 1950919 1935601 1918700 1901486 1885680 1870519 1858672 1844884 1827799 1813604 1793876 1778453 1762671 1747489 1730808 1717222 1702710 1687020 1673838 1661130 1645612 1627732 1609801 1595650 1578018 1564096 1549976 1536040 1520161 1508673 1495957 1478835 1462875 1452995 1435929 1420556 1410189 1397057 1383478 1369937 1356888 1341275 1330260 1313968 1301363 1284795 1272025 1262084 1247343 1235723 1221064 1211326 1197615 1186658 1171822 1158096 1146594 1136804 1123942 1111008 1097757 1086592 1074563 1064997 1052720 1039858 1028572 1018994 1007615 997938 983597 975462 964231 954114 945938 929469 921316 909429 898421 885466 875952 867212 854846 845812 835368 826199 815285 806569 798273 786490 777725 768888 758780 750591 742820 733219 723068 713894 705220 696985 689422 679650 670355 663888 654132 648189 639421 630324 622719 614788 607179 600029 593536 585585 578050 571912 561579 557104 548999 540971 534840 528963 522063 513584 508469 501215 494339 489119 481267 475358 470191 462928 458218 452735 444979 439828 434812 428975 422501 416077 411474 405358 401295 395233 388923 383503 378223 373267 368893 362755 356674 352387 348142 342651 337221 331555 328486 324019 320174 316020 310677 306275 304439 298463 294395 290692 285430 282868 277483 275178 271320 267877 264053 260499 256378 252891 248728 244537 242457 239057 234304 231139 227442 223978 221839 218215 214704 212568 209175 206846 204213 201284 197821 195606 193973 190397 186963 184749 183662 178816 177067 175114 172247 170332 166532 164867 162367 159603 157259 157575 153182 150964 148868 145962 144291 141726 140254 137738 136166 133823 133994 130347 128193 126646 125176 123173 121429 119872 117924 116114 114086 112008 110113 109168 108342 106034 104508 102619 100575 98728 96876 98212 94885 93002 91109 90606 89168 87711 84920 83839 82195 81390 80474 78269 77637 75825 74896 73889 72692 71887 70525 70288 69437 68699 67790 66919 65564 65000 63383 63445 61828 61038 61786 60234 58766 57436 57357 60434 54945 56373 53537 54146 52054 51794 50883 49782 48851 48257 48151 46662 46239 46112 44621 44438 44030 42910 42528 42102 41807 40886 40413 39314 39063 38298 37797 39208 38031 37423 37035 36607 36484 36561 35788 35484 34944 34179 33229 30749 30342 30058 29571 29054 28703 28175 28266 27484 27519 27020 26743 26141 25768 25516 25015 24968 24585 24411 23903 23558 23629 22753 22344 22849 22237 21930 21569 21258 20914 20767 20590 20254 19927 19389 19531 19159 19122 18651 18250 18159 18013 17660 17519 17245 16656 16779 16423 16289 16197 16013 15815 15532 15306 15125 15032 14955 14582 14460 14355 14015 14083 13876 13637 13368 13286 13298 13222 13133 12719 12884 12539 12496 12262 12142 11862 12094 11748 11723 11666 11527 11399 11576 11125 11071 11026 10900 10735 10716 10788 10404 10453 10298 10399 10402 10297 9928 9955 10140 9780 9634 9879 9348 9028 9316 9097 9218 9085 8940 9154 9061 8965 8885 8794 8765 8716 8720 8548 8601 8563 8343 8440 8212 7998 8261 8161 8024 7931 7843 7890 7765 7744 7780 7476 7535 7520 7619 7399 7358 7146 7311 7109 7095 6981 6880 6836 6856 6870 6744 6637 6555 6751 6694 6551 6422 6464 6408 6426 6569 6514 6414 6303 6406 6242 6260 6318 6279 6259 6169 6147 6017 5828 6109 6008 6166 5902 5889 5661 5744 5617 5578 5576 5317 5451 5695 5682 5491 5372 5504 5452 5430 5234 5157 5020 5271 5251 5203 5218 5166 5065 5092 4983 5134 5045 4866 4913 4867 4700 4650 4774 4685 4812 4686 4675 4550 4583 4570 4463 4341 4554 4314 4326 4320 4205 4282 4279 4121 4070 4210 4164 4153 4147 4147 3986 3957 4065 4076 3924 3904 3968 3840 3862 3760 3855 3823 3684 3677 3713 3731 3791 3706 3664 3493 3460 3599 3628 3460 3466 3415 3527 3528 3472 3376 3315 3359 3405 3351 3292 3275 3289 3798 3202 3226 3154 3182 3015 3009 3125 3125 3100 3068 3069 2977 3039 3043 2975 2954 2887 2920 2955 2835 2749 2864 2939 2838 2906 2968 2876 2912 2979 2948 2873 2910 2976 2954 2880 2841 2901 2833 2783 2837 2730 2742 2807 2818 2791 2879 2781 2886 2862 2749 2838 2988 2941 2970 2936 2843 2803 2849 2844 2830 2750 2803 2846 2861 2841 2832 3007 2722 2632 2810 2769 2892 2963 2712 2718 2728 2622 2638 2531 2389 2479 2335 2457 2464 2403 2279 2327 2322 2433 2282 2307 2278 2190 2195 2079 2222 2172 2124 2103 2125 2069 2013 2080 2108 2083 2141 2045 2114 2137 2116 1930 1961 2019 2043 2003 1991 2038 2026 1946 1938 1926 1907 1927 1930 1954 1897 1972 1965 1865 1922 1846 1861 1880 1827 1808 1935 1810 1809 1748 1805 1744 1822 1743 1765 1872 1697 1751 1728 1678 1624 1760 1804 1660 1706 1730 1697 1627 1706 1662 1709 1608 1611 1620 1631 1657 1632 1557 1591 2260 1611 1629 1570 1532 1544 1520 1523 1610 1443 1412 1505 1428 1418 1363 1461 1544 1557 1342 1345 1519 1374 1299 1295 1289 1350 1294 1294 1291 1291 1271 1300 1288 1406 1314 1293 1225 1213 1224 1232 1198 1291 1263 1260 1183 1180 1320 1074 1122 1139 1122 1118 1091 1145 1141 1030 1064 1043 1012 1103 1025 992 1113 1029 1046 962 1047 984 997 948 1000 1082 1008 1003 1022 1020 993 994 977 964 973 944 977 1044 1019 976 1009 977 975 944 903 895 967 865 968 890 809 876 857 923 811 832 806 819 876 876 850 867 932 877 819 862 806 871 824 780 810 785 775 817 809 803 798 800 826 827 797 821 845 816 797 796 861 825 799 780 835 804 724 770 748 699 733 738 716 732 766 717 723 759 713 656 770 716 666 707 671 697 694 685 628 644 624 622 657 672 661 617 696 637 616 619 672 695 708 714 719 689 684 694 629 641 618 674 759 680 686 701 701 635 717 669 637 630 669 711 623 629 632 608 640 615 595 626 606 640 598 594 587 559 561 647 656 616 639 550 572 512 581 559 558 566 529 547 559 503 549 504 490 494 537 551 540 532 569 500 509 515 524 510 490 556 517 506 536 508 553 558 542 497 478 473 527 464 432 505 518 505 500 485 522 512 514 472 488 505 502 481 476 511 470 518 458 480 494 522 472 474 458 534 499 486 479 458 488 479 470 488 536 501 467 467 501 499 482 461 458 546 472 442 458 504 487 430 418 463 404 443 414 445 434 455 406 452 454 377 417 428 473 445 375 407 459 446 460 426 387 406 367 398 447 419 418 385 437 394 398 387 412 407 407 404 400 452 384 387 455 406 435 435 417 458 510 531 474 484 442 420 401 405 409 406 401 383 381 370 363 405 465 391 337 362 385 385 366 341 364 385 342 339 360 347 391 359 333 356 351 365 345 348 365 382 334 392 382 362 366 360 392 247 280 261 224 249 232 247 236 250 242 252 250 219 275 255 234 250 261 258 370 273 256 295 240 267 259 264 268 272 242 271 247 223 251 229 245 256 277 244 231 229 231 220 216 245 265 252 241 221 234 234 219 242 235 236 266 310 268 300 276 249 286 291 269 275 286 262 252 246 251 299 208 232 234 275 266 241 244 244 226 219 211 223 226 232 234 226 234 225 235 229 201 206 192 238 220 177 189 208 187 175 210 207 213 189 183 181 199 196 170 172 196 182 147 162 183 188 164 177 199 191 164 187 198 167 178 153 203 181 205 168 189 180 185 172 171 185 162 147 179 189 163 172 199 177 173 138 171 169 171 166 176 155 187 148 173 157 154 137 151 151 165 181 166 186 141 173 167 181 165 196 174 176 173 193 181 202 183 179 201 215 204 215 229 261 229 239 223 214 234 236 229 219 223 204 257 212 216 216 240 214 231 178 213 243 149 126 136 140 133 143 143 144 124 136 109 143 114 137 138 127 134 118 121 121 105 99 111 145 123 116 114 116 104 94 122 101 103 128 115 114 120 123 111 103 105 107 111 123 92 136 119 116 117 106 108 128 105 96 134 117 93 122 92 108 124 101 104 109 127 103 101 102 108 79 203 100 110 94 94 101 91 104 78 81 89 91 97 91 93 94 90 89 89 99 95 85 99 99 75 96 104 110 93 85 86 78 88 100 85 76 90 92 82 96 92 114 101 118 115 84 94 90 101 107 94 102 91 108 91 96 95 111 75 98 105 86 90 79 85 96 95 92 88 83 98 75 63 78 86 68 82 96 101 96 94 84 111 108 108 89 95 89 93 76 105 82 77 82 94 90 95 92 93 87 80 86 91 75 86 104 104 117 107 65 91 81 81 88 106 94 108 102 92 111 75 107 88 74 89 75 81 90 82 69 83 88 91 77 88 76 88 85 94 64 77 105 82 74 74 70 65 74 78 84 76 94 56 67 68 75 84 71 74 62 63 74 76 79 69 84 73 74 83 86 70 100 69 74 72 66 77 69 67 63 79 63 70 81 73 71 72 75 68 75 73 57 66 70 68 81 84 72 62 42 61 65 67 52 63 81 58 68 64 55 53 67 55 57 63 64 63 65 51 77 52 51 48 57 52 50 57 61 41 45 60 50 44 65 54 66 58 61 43 57 64 66 62 60 43 57 48 60 64 62 57 49 63 51 39 69 52 60 45 51 58 49 48 55 42 48 45 40 38 48 55 44 50 48 53 34 43 55 53 42 34 51 55 41 65 51 49 54 51 60 42 49 56 61 57 43 47 48 56 58 64 59 52 58 43 44 56 60 41 47 53 71 52 59 52 54 54 48 50 59 65 48 49 49 47 52 40 51 43 45 47 50 47 46 50 53 53 53 51 48 42 35 40 33 63 44 49 51 54 47 43 55 42 55 47 47 53 51 46 51 69 48 53 46 46 54 58 59 45 61 56 57 53 64 60 54 65 51 61 59 61 71 47 59 68 46 50 65 48 65 70 52 40 69 54 56 41 55 38 71 60 63 59 59 58 54 71 63 76 69 66 52 76 55 62 61 57 78 66 63 58 52 47 55 47 52 38 63 52 53 64 36 46 57 40 46 43 44 42 50 45 51 40 39 38 46 43 46 63 50 48 62 49 41 44 46 54 45 42 46 57 54 63 61 42 44 59 35 56 49 48 45 48 45 43 48 55 41 49 53 43 55 52 53 49 40 45 54 45 58 40 
];
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
 996969 338980 657989
 1249146 431507 817639
 1238366 440259 798107
 1180600 425026 755574
 1534058 552938 981120
 1367111 499785 867326
 1576032 581536 994496
 2937363 1027048 1910315
 1502291 563958 938333
 1739576 657204 1082372
 2815194 996379 1818815
 1705739 650055 1055684
 2698083 972515 1725568
 1592139 610541 981598
 1786305 693804 1092501
 2726667 994440 1732227
 1868977 729386 1139591
 2657857 980974 1676883
 1877159 747198 1129961
 2642194 995887 1646307
 1742519 702320 1040199
 2944585 1118837 1825748
 1700166 698589 1001577
 2851090 1094646 1756444
 1595598 659112 936486
 3014677 1178878 1835799
 2967151 1179062 1788089
 1687396 715344 972052
 2936457 1170263 1766194
 1435780 627211 808569
 122978119 55580005 67398114
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
116 291 1 1
69 23 0 3
115 59 1 0
89 56 1 0
55 63 2 0
72 92 7 5
331 136 18 9
4602 197 30 12
57445 235 108 40
448661 381 192 124
1235862 556 290 199
2369891 1045 476 386
3578921 2109 754 581
5183264 5120 1246 1087
6717633 11461 1863 1723
8301454 25114 3050 2874
8789038 48036 4721 4683
7677641 77871 7144 6882
5105136 110326 10146 9711
2144383 141116 13399 12972
470331 168525 16253 16170
71355 191309 18982 19100
38759 198341 21828 21428
34361 179244 23286 23201
30934 143742 24832 24399
29394 106861 25130 25371
28045 77031 25742 26101
27486 57503 26698 26524
28470 46872 27438 27220
28936 40664 29214 28797
29640 37380 29927 30062
32439 36702 31048 31585
36778 37626 32469 32556
39290 39133 34630 34542
40020 40039 37095 37111
41940 42062 40244 40210
45891 45225 43483 44101
50415 49621 48620 48872
54464 54054 53752 53917
59275 59255 58882 59231
66056 67240 65744 66516
73995 74352 74550 74141
83825 84006 83576 83551
94537 94695 94871 94480
107852 108052 107769 108018
122982 124388 123671 124779
139267 140681 141490 140517
154841 155408 155478 155928
173023 173683 173300 173057
193148 192865 191587 191228
210723 209437 209694 210152
225862 226352 225964 227096
240938 241338 239927 239919
255445 256292 255433 255439
272821 271195 272634 272506
279431 279754 279374 279025
292922 295058 293688 293336
303176 302939 302230 301649
306806 307587 307042 307036
312890 314761 312721 314313
324046 324503 322726 323729
315861 313517 313030 316228
294270 294539 294876 295741
248747 249711 248919 249820
182161 183508 183544 181973
103926 104032 103536 103382
49863 51374 49361 53262
37503 36615 36539 37146
37883 37388 34368 37924
29006 32310 33985 29791
21997 23341 21848 24956
19200 16951 15908 18777
776 1048 586 335
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
