A = [
950198 826114 3509973 836118 845151 801344 788129 795156 792084 777007 796571 841311 878981 938215 1028713 1087515 1140621 1215374 1227346 1223357 1238485 1218248 1198820 1195242 1205362 1441642 1451720 1466499 1684054 1491344 1505788 1490668 1310422 1333405 1314467 1313652 1305948 1281860 1277257 1261915 1256604 1251987 1260979 1259314 1257233 1265663 1246733 1236570 1230902 1205470 1197397 1194170 1189538 1187205 1178293 1175485 1168667 1163037 1154512 1145445 1137193 1131672 1126122 1120579 1116788 1107670 1103752 1093060 1093332 1081093 1071460 1064240 1053832 1047939 1043048 1034054 1026771 1018436 1010544 998884 993909 982884 976123 967480 959764 952398 946372 936156 929757 921135 912496 903015 895992 887269 881610 873504 863752 856308 850525 845337 834716 825375 819586 809874 802742 794773 788496 779705 773056 768735 760065 753143 747449 736604 729588 723581 717915 710356 705101 698443 689034 684420 676605 672532 662071 654986 647787 640343 635112 628346 621689 615442 608722 601445 597160 590180 585815 578290 571204 566455 560465 553245 548850 541694 535115 530113 524762 519981 512988 507334 501746 496145 490869 486834 478133 475794 468112 463960 458679 453421 448256 442710 438632 434289 428411 423536 418063 414360 408385 403583 399158 393058 389904 387009 380374 376685 371525 367001 362758 359198 354229 350266 345729 341571 338482 334437 329880 324685 321748 317598 313812 310943 306477 302821 299532 295347 293005 287556 284385 282626 278070 274260 268687 265668 262760 258745 256379 251840 249316 246203 244076 239343 236418 231950 229465 227227 223817 221040 218486 215270 212012 209701 207597 204328 201833 198321 196890 194162 191788 189367 187045 184094 181781 178751 175390 175294 171278 170076 167231 164711 162354 159920 158747 156405 154981 152231 150719 148112 146802 145298 142844 141224 138923 137398 134820 133112 130691 129697 128051 125637 124719 122483 120317 120321 118122 116426 114915 113749 112447 110899 110103 108632 106918 105220 103527 102036 100383 102086 96995 96002 97493 93794 92826 91246 89574 88889 87175 87359 89844 85057 83355 81875 80901 79964 78627 77941 76897 75709 74675 74779 72746 71449 70938 69281 68684 67841 67053 66280 65144 63972 63162 62521 61751 61342 60100 59574 58079 57372 56040 56287 56997 54572 53505 52226 51817 51058 50865 48789 48656 47926 47343 46617 46443 45481 44830 43760 43519 43220 43401 41735 41029 41350 40619 40069 39517 38909 38430 38226 37705 36863 36585 37510 35661 34601 34401 34574 39041 34057 33072 32519 32295 31714 31837 31166 31139 30123 29879 30382 29070 29040 28594 28131 27896 27364 27136 26583 26592 27342 26421 25569 25397 24667 24185 24316 25681 25190 24727 24953 24594 24402 24386 23795 23266 23479 22886 22811 22434 21993 22270 21622 21731 21964 21010 21130 21304 20642 20353 20126 19892 19314 19687 19277 19730 19373 19429 18816 18746 18604 18426 17851 17656 18692 17641 16910 17992 16662 16856 16726 16949 16787 16615 17552 16644 17930 16212 15636 15603 15487 15118 16174 15344 14707 14647 14693 14263 14449 14263 14482 14723 13925 13991 13851 13778 12982 13352 13116 13220 12857 13116 13168 12817 13691 13004 13362 13345 12546 13005 13021 12657 12371 12069 12618 12296 12407 12100 12160 11926 12216 11664 12082 11832 12056 11515 11439 11772 11763 11650 11251 11176 11597 10691 11257 10961 10784 11153 10859 10875 10582 10854 10505 10691 11102 10641 10696 10759 10623 10658 10721 10759 10533 11276 10509 10949 10623 10057 10542 9932 10416 10444 9728 9734 9801 9583 9249 9667 9377 9580 9509 9445 9235 8840 9302 9102 9158 9691 9245 9149 10619 9552 8949 8978 8588 8410 8435 8450 8558 9465 8608 9494 8367 8210 8505 8419 8074 8010 8049 7984 8280 8319 8250 7975 7928 7472 8039 7592 7279 7104 7166 7291 7202 7430 7683 6944 6711 7160 7063 7182 7200 7323 7266 7582 7551 7017 6841 7057 7511 7601 7607 7207 6598 6768 6998 6785 6545 6484 6666 6715 6500 6681 6537 6467 6754 7493 7024 7487 7561 7725 8156 7776 7759 7081 7553 7047 7503 8876 7058 7079 7209 7174 7682 7221 7573 9058 7240 6807 6823 6808 6554 7776 6656 6666 7328 6761 6570 7194 8082 7292 7748 6411 6452 6496 6875 6851 6696 6548 7151 6870 6482 6514 6290 6456 6795 6531 6931 6973 7241 6717 6934 6791 6863 6637 6711 6906 7212 6651 7279 7073 6656 6465 6823 6536 6582 6474 6371 6297 6534 6341 6732 6683 6751 6503 6463 7425 7330 6738 6787 6564 6419 6750 6686 6570 6276 6811 7781 6651 7214 7098 6676 6522 7635 6568 6914 6929 6576 6842 7203 6862 6623 7190 6923 6833 6582 6896 6852 7695 7724 10725 8556 8246 7500 7293 7580 8631 8047 7471 6485 6336 6543 6485 6483 6747 6561 7045 7277 7071 7007 7066 7276 7064 6975 6608 6475 7100 8190 6412 6456 7484 6729 5754 7357 8809 7488 7678 7576 6760 6532 6562 6393 6093 5889 5799 5507 5395 5282 5228 5194 5758 4485 4721 4453 4514 4432 4438 4547 4642 4823 4642 4351 4923 4671 4462 4366 4351 4327 4158 4465 4440 6718 4355 4296 4369 4525 4867 4240 4390 5427 4154 4373 4319 4226 4202 3990 4180 4308 4051 4047 3853 3970 3884 3930 3889 3787 4313 3889 3966 3968 3802 3874 3887 3843 3847 4888 4759 5167 5157 5286 6347 5941 5439 5495 5336 5309 5827 5020 5508 5817 5935 6378 5564 5945 6282 5668 6050 5579 6267 6176 5469 5609 5668 5610 5389 5499 5526 5783 5939 5950 6126 5560 6266 5982 5344 5612 5748 6160 5647 5626 6085 5708 6451 6716 7712 5683 5360 5828 6011 5713 5085 5134 5092 4502 3317 3071 3089 4177 3122 3044 3334 3246 3169 3216 3210 3262 3199 3197 3305 3177 3721 5171 5178 5361 5055 5390 4861 5001 4726 4980 4956 4972 4906 6982 5750 7559 4942 6980 4809 4714 5026 4515 5137 5293 4982 4763 4356 4768 6616 4906 4112 4115 4218 4511 4201 4521 4376 4341 4375 4382 4424 5141 4650 4415 5618 4416 5805 4180 3783 4488 4355 3885 4390 3629 3155 2882 3055 2967 2870 3082 2978 2770 2970 2784 3071 2950 2967 3039 2913 2792 3063 2743 2783 2888 2928 3064 2784 2825 3092 3014 2778 2795 3020 2943 3050 2909 3195 2884 2865 3002 3064 3480 3029 3211 3181 3343 2977 2889 2729 2937 2971 2817 2933 2902 3071 2781 2979 2909 3139 2978 3002 3034 3396 3087 2739 3069 3058 3023 3057 2872 2751 3086 3179 2832 2948 2825 2904 3056 2837 2815 3029 2889 2781 2992 2841 2855 2884 2891 2749 3025 2912 2718 2869 2782 2970 2786 2815 2814 2966 2759 2790 2932 2969 3194 2844 2838 2894 3117 3226 2882 2948 2923 3329 2880 3010 3083 3004 3135 3005 3457 3144 2966 2976 2889 3117 2899 2855 2911 2826 2846 2768 2931 2738 2880 2805 3033 2700 2752 2719 2891 3066 3108 2754 2973 2913 2965 2959 2794 2800 2697 2663 2621 2706 2694 2895 2986 2723 3120 3076 3307 3905 3508 3849 3747 3668 3324 3264 3385 3512 3200 3549 3412 3605 3337 3397 3567 3432 3243 3531 3335 3313 3886 3188 3486 3170 3431 3219 3473 3548 3160 3213 2953 3017 2875 3181 3043 3343 3697 3461 3653 3452 3161 3471 3446 3212 3227 3207 3012 3053 3092 2938 2814 2902 3288 2806 2666 2741 4689 2451 2400 2278 2452 2264 2228 2157 2147 2383 2331 2249 2248 2416 2123 2162 2743 2504 2530 2196 2359 2154 2852 2470 2579 2584 2599 2781 2727 2783 2993 2668 2651 2787 2853 2829 3123 2753 2902 2949 3305 3119 2687 2668 2846 2849 2590 2856 2949 2995 2812 2885 2762 2385 2383 2619 2614 2866 2891 2743 2768 2760 3106 3128 3156 3616 3375 3237 3076 3058 3398 3500 2939 2925 3259 3226 2887 3012 3038 2890 2870 2816 3058 2947 3169 2872 2785 2267 2106 2195 2132 2280 2211 2352 2174 2321 2277 2418 2436 2462 2494 2381 2434 2564 2623 2631 2599 2500 2376 2516 2366 2601 2317 2194 2422 2218 2286 3218 2256 2240 2309 2388 2385 2221 2234 2401 2550 2499 3123 2627 2635 2490 2551 2533 3292 2548 2390 2436 2436 2357 2374 2461 2326 2450 2276 2334 2429 2365 2275 2226 2338 2305 2443 2396 2055 2417 2672 4564 4792 4566 2305 4725 4839 5124 5277 4737 5497 5007 6489 7379 5075 5422 4681 5783 7256 5056 5774 7423 5508 6390 6443 5440 5237 6162 5575 7104 8505 6876 6457 5923 5574 5914 6843 5904 5341 5333 5258 5800 6526 6528 6837 6733 6234 5829 5719 5051 5926 5721 4922 6129 7044 5535 6587 6766 6239 6975 6192 5510 5003 4729 5639 4571 4821 8015 6620 6623 6081 5662 4162 5050 5255 5837 5870 6050 6746 6824 7214 4625 4487 4427 4104 3971 3866 3944 3218 3317 3955 4186 4640 4507 5029 5180 4964 4112 4292 3777 4451 6507 4311 6531 7629 5554 5405 5961 4937 4762 5015 4591 3584 3295 4047 3813 3820 4368 5470 4717 4669 4299 4020 4134 3872 4130 3648 3641 3604 4425 4953 4433 4452 4531 4156 4026 4422 3673 3705 3776 3089 3687 4088 4619 4324 4330 4298 3945 2907 3759 2122 2181 2108 2102 2069 2000 2128 2325 2005 2095 1979 2100 2058 2087 1995 2140 2101 2101 2155 2192 2332 2311 2153 2211 2216 2379 2289 2278 2445 2255 2554 2218 2203 2049 2179 2156 2143 2147 1945 2175 2034 2067 1986 2279 1935 2038 2620 1943 2013 1957 2211 2113 1994 2204 2238 2289 2477 2568 2773 4899 5481 4629 4424 3508 4687 4103 3830 4490 4220 4533 5085 5129 5111 6015 5231 4069 1957 4178 6130 4043 4412 4307 4611 4934 5065 5900 4595 4194 3637 3818 3256 2244 2249 2200 2149 3655 2128 2153 2102 2132 2131 2321 2141 2165 2703 2095 2139 2111 2102 2276 2064 2004 2034 2077 2022 2048 2450 2094 2097 2135 2106 1947 1905 2095 1834 1898 1841 1915 1930 1853 1910 1936 1932 1954 1889 1790 1972 1873 2106 1859 1801 1949 1894 1758 1887 1869 1893 1933 1944 1743 1901 1850 1884 1921 1783 1792 1899 1923 1805 1767 2026 1771 1765 1866 2097 1764 1981 1942 1807 1868 1823 1752 1764 1741 1853 1796 1997 1803 1863 1902 1835 1824 2067 1952 1965 1938 1956 2429 2283 1985 2171 1883 1846 1871 1904 1861 1877 1870 1925 2190 1844 2096 1912 1829 1840 1879 1677 1799 1763 1834 1723 1960 1682 1778 1954 1648 1628 1874 1698 1658 1572 1664 1698 1638 1629 1666 1594 1609 1639 1638 1641 1810 1707 1735 1843 1729 1673 1687 1589 1696 1688 1626 1706 1689 1616 1749 1725 1937 1776 1778 1746 1899 1820 1751 1677 1725 1717 1732 1718 1797 1864 1727 1965 1902 1752 1919 1776 2051 1800 1809 2059 1947 1871 1885 1909 1989 1961 1933 1935 2040 2022 1951 1931 2063 1901 1959 2076 2014 2066 2081 2144 2034 1970 2235 2191 2094 1930 1971 2464 2533 2149 1990 2165 2143 7578 2070 1966 2069 2134 2175 2066 2082 1941 2045 1979 2051 1850 1951 2012 1894 1946 1906 1863 1876 1955 2308 2004 2060 2003 1943 1962 1922 2010 2042 1847 1955 1976 1811 1845 1866 1891 1804 1958 1822 2094 1892 1905 1778 1766 1761 1875 1869 1890 1728 1816 1753 1694 1788 1658 1775 2290 1751 1882 1756 1899 1805 1750 1613 1752 1730 3342 1787 1641 1702 2101 1661 1661 1721 1630 1614 1607 1563 1620 1590 1817 1578 1519 1725 1771 1653 1696 1657 1649 1706 1688 1660 1958 1613 1952 1856 1725 2442 1692 1710 3078 1785 1696 1614 1702 1654 1681 2062 1521 1748 1709 1556 1710 1640 1660 1687 1605 1694 1522 1558 1749 1599 1573 1672 1676 1756 1706 1718 1699 1729 1807 1783 1852 1779 1794 1873 1949 1764 1990 1760 1610 1825 1744 1744 1684 1707 2170 1816 1734 1781 1743 1888 1879 1738 1904 1902 1841 1914 2405 1867 1896 1820 1769 1786 1924 1862 1929 2053 1971 1921 2074 1980 1979 2659 2004 1806 6482 1829 2074 1958 1941 1910 1973 1891 1730 1882 1895 1799 2020 1931 1824 1888 1859 1885 1874 1791 2086 1775 1804 1762 1833 1882 1802 1750 1791 1748 1758 1750 1661 1865 1821 1793 1729 1776 1895 1870 1887 1912 1856 1923 2057 1896 1895 2039 1729 1681 1808 
];
B = [
0 0 0
 1357439 86967 1270472
 1369415 94931 1274484
 1469435 96497 1372938
 2139675 160042 1979633
 1278428 93113 1185315
 4717230 452035 4265195
 1951829 168842 1782987
 1190000 117472 1072528
 1146697 123963 1022734
 879669 85259 794410
 638862 61791 577071
 429926 46144 383782
 340160 38162 301998
 697131 73303 623828
 624818 63909 560909
 571862 58036 513826
 1629714 189826 1439888
 1092653 111875 980778
 974005 108002 866003
 728719 83079 645640
 832774 108292 724482
 812513 110621 701892
 633022 87235 545787
 782695 111738 670957
 634759 91227 543532
 1179450 166756 1012694
 983027 143339 839688
 786388 119730 666658
 978285 155228 823057
 810701 133898 676803
 1012611 170838 841773
 996510 177020 819490
 946786 171590 775196
 1229452 222569 1006883
 1092396 202264 890132
 1256280 234925 1021355
 2384722 419691 1965031
 1191094 229303 961791
 1378478 268726 1109752
 2274019 412695 1861324
 1346652 267516 1079136
 2169759 404192 1765567
 1255131 251160 1003971
 1402765 286460 1116305
 2182043 416565 1765478
 1466397 301952 1164445
 2121845 410708 1711137
 1461777 311495 1150282
 2097739 417654 1680085
 1351900 293681 1058219
 2328902 470949 1857953
 1311687 293142 1018545
 2246386 462167 1784219
 1229784 277836 951948
 2364924 496927 1867997
 2316708 501229 1815479
 1288744 302003 986741
 2289031 496742 1792289
 1086971 265482 821489
 92008018 24046521 67961497
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
76 141 0 0
34 17 1 2
65 39 2 0
65 42 1 1
54 47 2 1
81 78 3 4
245 92 10 2
2331 137 14 4
26834 180 36 26
209545 290 86 47
575108 421 112 80
1105218 752 220 183
1668572 1233 329 270
2418395 2726 551 503
3138131 5653 854 771
3877323 11885 1383 1301
4102904 22612 2089 2071
3579724 36463 3090 3051
2378985 52066 4468 4357
1000465 66583 5972 5787
222863 80034 7314 7249
35771 90191 8798 8842
20561 93677 9901 10095
18570 85323 10778 10849
16931 68864 11762 11428
16016 51053 12450 12025
15070 37437 12655 12681
15070 29272 13097 12946
15374 23917 13020 13298
15268 20657 13574 13680
15319 19620 14655 14503
16828 18755 15284 15576
19197 20135 16151 16007
21375 20826 17431 17109
21279 21796 18803 18405
22933 23254 20336 20371
25147 24621 22159 22303
27546 27508 24835 24500
28865 28718 27791 27118
30921 30756 29829 30453
34397 35136 33433 33822
38559 38761 38726 38236
43676 44002 43733 43360
48894 49348 49220 48889
55614 55451 55621 55505
62807 62902 62658 62811
70614 71246 71538 70880
79512 79876 79981 80029
88898 90219 89240 88808
99117 99180 98745 98577
108413 107923 107616 108077
116790 116671 116030 116436
123233 123018 123168 122800
129204 129606 129641 129478
134302 133718 134109 133069
139506 139393 138982 139439
144853 145309 143950 144206
148979 148731 148884 147754
151549 152309 151862 151889
153269 153720 153477 153999
152843 152487 152764 152464
148288 148061 147591 147583
135252 134782 136333 136251
112899 113882 113067 113628
78234 78176 78345 77391
39955 39887 39996 39852
14181 14362 14323 14363
2619 2443 2482 2472
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
