A = [
3795703 4030435 91935452 10111369 3393090 3479444 8781645 3743356 3439252 3355513 3458173 3405155 3395659 3303541 3370401 3343505 3284445 3324431 3244021 3076196 2930895 2841599 2716258 2633267 2680853 3216657 3285924 3381661 3879331 3652044 3638415 3579702 3386665 3377961 3340262 3384889 3304504 3247823 3271486 3208467 3191293 3215347 3163392 3154563 3170724 3129044 3104702 3110109 3052906 3034502 3056824 3009629 2989496 3018035 2982554 2951410 2963500 2921222 2905493 2903901 2868903 2858001 2871444 2830692 2829491 2837035 2794630 2784094 2784349 2747375 2744535 2749817 2718189 2715025 2727559 2688571 2683967 2693068 2657541 2636193 2649966 2620043 2604976 2613106 2585383 2577571 2582723 2551741 2548453 2548464 2513302 2503526 2515338 2484698 2475713 2479301 2463740 2451921 2453324 2430627 2418742 2422150 2391032 2392447 2401735 2374455 2368432 2365161 2353736 2341295 2346776 2327375 2313235 2325788 2303340 2312676 2343388 2325558 2327483 2346578 2325013 2325570 2321172 2293781 2294798 2297994 2271983 2266148 2271519 2245217 2247073 2239306 2210532 2208924 2216569 2192807 2188922 2197978 2171457 2157267 2163296 2140325 2129135 2128619 2112047 2110875 2106299 2089770 2079990 2084154 2061851 2060152 2052731 2031523 2027811 2027493 2011810 2008817 2004913 1985863 1986723 1981892 1962251 1957361 1951539 1934998 1928960 1931226 1914525 1908685 1906550 1892493 1889449 1884619 1867856 1856059 1859750 1842657 1833132 1828835 1816880 1812623 1804647 1790552 1787128 1781272 1767439 1763569 1761152 1750842 1742478 1737234 1725913 1716505 1719325 1704276 1695235 1693703 1680092 1675738 1672494 1657880 1658650 1652841 1633402 1627456 1625818 1613277 1611187 1605996 1598556 1588767 1584482 1572577 1566567 1560495 1549058 1542737 1543299 1530664 1523077 1522716 1511675 1506769 1504160 1486963 1486140 1483477 1468519 1466646 1457552 1446681 1440364 1442060 1429345 1422431 1418055 1410485 1399547 1397321 1393385 1387536 1377850 1368940 1361168 1360871 1349386 1343778 1338680 1327665 1324244 1318424 1310118 1306274 1295297 1293558 1281881 1281707 1271883 1268429 1262973 1250283 1245729 1239320 1231684 1229521 1222958 1213700 1210430 1206190 1197583 1190908 1183735 1182225 1171373 1164338 1160848 1153013 1149562 1141452 1134628 1124345 1120861 1110929 1108953 1102004 1094205 1092816 1079818 1077018 1075290 1066422 1056675 1053442 1042839 1040590 1033013 1026227 1022696 1014283 1010411 1003433 995771 988396 981836 977131 969906 966038 960189 953678 948605 943635 933617 927326 923582 916636 909203 903182 897386 892702 887315 876548 874693 862874 859700 852112 846326 840067 835334 826764 823387 815705 811094 803487 799298 793806 786660 781512 777201 768414 763589 758129 752191 743448 738479 730947 726476 722411 713238 710672 705182 697879 690644 686343 679051 673812 670077 663603 656051 654345 646362 643799 637712 630027 625399 620051 612101 605393 601927 595547 590471 586358 581392 577003 572528 567396 562773 557047 550110 546923 541359 534008 531835 529095 518959 515623 513424 505734 500544 494828 490109 488581 481567 477233 473717 470583 463383 459015 452775 448838 444979 440721 436876 430260 425317 422564 418744 413171 407199 405337 399968 395733 391635 387157 382451 378284 374271 369824 365529 361137 356573 354921 350359 343985 343374 337247 333043 329949 326911 323821 320170 315356 313343 310422 305457 301585 297870 294622 289686 286505 283833 280053 276335 273796 269283 267199 263517 260768 259078 255314 251607 248700 245565 244030 239586 237306 233723 229792 227291 224845 222407 218645 216354 214301 211438 209489 205306 203343 200248 196368 193953 191648 189126 187108 184579 181012 179978 177010 174845 172870 170491 168012 165689 163962 160758 159112 157221 154796 153251 151405 149376 146930 144778 143168 140584 139920 137518 135290 133060 132014 130690 128034 125949 123407 123447 121568 118384 118521 116029 114533 112857 111589 110007 107909 107745 105211 104459 102583 100273 99979 98885 97652 95165 93846 92811 91668 90007 88255 87809 86499 84961 83900 82606 81795 80083 79516 78941 77734 76790 75021 74131 73630 72194 72035 70475 69395 68106 66862 66265 65309 64212 63373 62584 62035 60467 59865 59187 58341 57345 56529 55703 55044 54309 53271 52883 52550 51041 50983 50181 49695 48879 48314 47140 46936 46004 45218 44545 44234 43619 43073 42750 41592 41312 40646 40793 39147 38957 38888 38299 37943 37082 36671 35936 35783 35200 34689 34570 33902 33536 32941 32880 32053 32001 31145 31260 30706 29843 29517 29531 28810 28449 28097 27811 27396 27047 27058 26364 25957 25865 25618 25118 24545 24447 24241 23789 23629 23198 23124 22737 22441 22112 22164 21577 21451 21547 20818 20648 20466 20044 20028 19790 19477 19205 18984 18976 18778 18364 18404 18102 17955 17750 17288 17285 17248 17001 16519 16737 16331 15975 16079 15914 15287 15536 15349 15158 14943 14844 14523 14255 14092 13870 13850 13890 13664 13411 13487 13277 13261 12930 12893 12676 12425 12697 12334 12009 12030 11947 11731 11583 11532 11479 11503 11146 11241 11196 11130 11091 10852 10840 10615 10435 10586 10228 10280 10428 10014 10019 10173 9923 9638 9543 9430 9444 9366 9224 9086 9046 8914 9146 8970 8776 8617 8668 8588 8678 8326 8361 8337 8116 8394 8346 8360 8218 8121 7965 7885 7741 7830 8116 7721 7614 7627 7695 7518 7246 7259 7266 7313 7336 7246 7190 7144 6920 7006 6962 6932 6807 6988 6845 6774 6868 6575 6254 6417 6495 6262 6235 6330 6231 6108 6281 5994 6038 5913 6018 5947 5919 6051 5885 6386 5886 5872 5769 5797 5761 5783 5615 5643 5492 5653 5857 5344 5378 5508 5306 5421 5383 5542 5410 5289 5448 5216 5322 5273 5012 5021 5212 4831 5015 5050 4935 4971 5061 4933 4994 4963 4886 5003 5012 5064 4745 4950 4798 4736 4700 4630 4604 4554 4695 4713 4743 4507 4662 4738 4568 4541 4553 4638 4454 4386 4462 4354 4300 4274 4260 4223 4408 4373 4360 4268 4326 4148 4200 4290 4159 4252 4285 4092 3924 4225 4022 4118 4052 4150 3964 4167 4004 4113 3970 4048 4078 3890 3846 3944 3846 4083 3931 3810 4048 3752 3917 3721 3793 3682 3822 3889 3705 3736 3711 3808 3754 3825 3557 3645 3643 3536 3638 3663 3689 3539 3613 3476 3533 3472 3487 3631 3526 3635 3492 3658 3530 3290 3281 3387 3410 3368 3265 3385 3324 3364 3280 3366 3317 3283 3278 3179 3353 3105 3117 3032 3164 3070 3224 3059 3031 3096 3132 3016 2968 2995 3076 2961 3026 3020 3013 2910 3174 2950 2969 2967 2973 2836 2933 2887 2916 2922 2902 2754 2828 2758 2761 2688 2856 2731 2734 2642 2870 2779 2713 2687 2717 2698 2767 2665 2637 2501 2543 2623 2627 2640 2648 2720 2544 2680 2595 2737 2601 2557 2565 2494 2453 2537 2415 2497 2497 2387 2415 2434 2378 2418 2415 2414 2568 2358 2306 2818 2370 2435 2483 2318 2385 2281 2406 2347 2357 2297 2316 2391 2335 2343 2378 2250 2274 2227 2263 2252 2093 2220 2278 2286 2204 2101 2270 2129 2101 2214 2137 2531 2066 2095 2052 2207 2072 2107 1978 2146 1965 2020 1983 1969 1966 2020 1990 1924 2000 1950 1887 1994 1942 1942 1961 1969 1910 1991 1932 1875 1947 1935 1916 1884 1885 1885 1869 1898 1814 1943 1902 1980 1770 1879 1964 1926 1819 1876 1851 1931 1928 1934 1787 1774 1876 1924 1817 1802 1819 1771 1687 1788 1729 1726 1746 1750 1700 1764 1971 1840 1711 1708 1728 1677 1684 1792 1659 1645 1814 1747 1642 1596 1700 1613 1641 1591 1688 1717 1712 1642 1605 1726 1701 1612 1628 1633 1702 1588 1591 1632 1564 1540 1476 1487 1462 1570 1582 1550 1561 1572 1525 1474 1455 1534 1481 1545 1458 1418 1440 1442 1522 1418 1421 1416 1388 1440 1429 1566 1524 1435 1482 1423 1438 1396 1396 1487 1517 1492 1398 1758 1440 1481 1386 1457 1447 1348 1436 1392 1350 1434 1358 1425 1466 1347 1383 1414 1436 1316 1350 1375 1352 1329 1380 1314 1330 1267 1285 1282 1347 1246 1306 1206 1188 1276 1301 1241 1193 1206 1291 1223 1294 1239 1280 1251 1254 1335 1303 1176 1203 1317 1228 1295 1337 1219 1242 1293 1199 1238 1215 1233 1226 1182 1180 1187 1277 1224 1162 1163 1120 1181 1082 1145 1208 1159 1171 1132 1109 1141 1094 1149 1116 1092 1069 1149 1111 1085 1095 1102 1072 1145 1060 1087 990 1077 1088 1113 1056 1103 1044 1134 1096 1023 1022 1005 1013 1037 1021 968 971 992 1033 1056 1067 1000 997 943 962 994 1004 992 951 968 1018 991 1043 958 924 925 874 952 911 928 972 879 893 864 843 862 861 978 934 939 856 850 884 825 811 859 800 834 846 877 848 798 857 779 952 864 783 843 815 762 812 723 756 766 901 765 736 783 756 787 731 753 821 754 769 747 781 794 755 719 817 781 771 763 797 746 748 729 735 723 746 837 721 746 734 1144 747 745 710 739 701 733 714 731 693 730 762 791 777 741 775 721 763 727 718 709 738 724 774 708 806 764 757 769 709 744 738 747 733 771 765 787 761 784 734 692 701 741 708 704 739 681 698 664 679 667 693 674 660 660 665 641 631 633 641 647 670 624 713 583 660 678 634 613 591 669 585 603 666 557 595 610 676 667 671 599 588 621 577 623 602 577 538 608 641 645 600 596 614 628 582 577 667 560 594 587 573 549 599 556 517 575 541 548 549 549 603 522 524 573 573 559 620 537 530 564 529 505 574 505 432 538 565 513 554 516 545 502 475 519 527 512 532 492 556 525 532 497 536 671 557 557 513 500 459 480 536 520 528 480 512 503 508 544 804 535 492 525 481 457 505 473 500 527 534 505 477 495 515 484 482 478 481 543 484 552 548 513 495 491 513 490 468 506 472 509 457 479 477 445 455 468 466 510 488 524 498 491 471 503 422 417 431 473 421 447 424 398 410 450 401 401 391 439 409 406 373 367 398 390 434 409 412 433 370 373 372 430 400 395 381 354 446 461 406 391 401 391 451 385 433 442 367 369 382 401 444 380 408 521 404 376 370 375 413 406 362 370 369 452 400 378 379 371 446 378 363 383 395 359 359 400 400 362 421 372 387 374 399 367 375 367 381 406 336 368 371 362 307 332 353 374 384 376 375 362 344 341 348 374 352 371 344 346 312 344 353 344 337 321 325 347 344 378 375 302 313 353 350 344 281 321 310 318 320 330 331 304 356 331 318 305 319 357 295 321 316 280 288 325 314 303 325 343 322 326 288 295 327 314 318 297 294 294 327 315 313 291 307 377 303 282 286 335 350 315 326 302 296 298 336 348 309 306 329 302 325 312 291 323 336 318 303 308 291 314 259 269 315 325 290 467 297 332 315 346 265 299 311 301 324 271 275 299 279 288 287 260 261 279 269 229 269 261 272 261 265 274 263 271 289 252 271 230 238 245 290 287 241 261 273 255 250 251 225 231 239 259 241 275 230 275 251 567 251 289 269 265 254 275 264 261 260 274 239 265 246 258 260 211 226 244 250 230 200 224 228 228 207 194 214 232 243 229 241 206 220 201 213 211 207 215 199 223 217 222 200 245 217 220 210 208 224 220 246 232 192 211 185 248 232 216 209 235 203 194 221 201 183 215 220 196 209 205 200 217 189 189 187 221 199 203 198 216 212 220 184 187 184 157 157 181 189 189 211 168 180 185 184 157 185 188 188 151 158 159 143 153 177 193 162 163 182 157 174 151 168 162 144 184 150 139 157 178 174 176 172 169 174 174 179 180 168 156 175 136 168 163 162 153 174 146 172 179 164 181 171 181 156 182 192 174 185 164 184 219 166 194 160 164 180 179 192 165 161 192 165 173 174 166 176 167 164 169 183 164 151 154 172 139 176 172 
];
B = [
0 0 0
 562353 312550 249803
 449841 232151 217690
 630071 329661 300410
 557593 306732 250861
 578377 321625 256752
 667165 414892 252273
 498757 309895 188862
 1117843 749715 368128
 397711 261701 136010
 436281 276228 160053
 411067 266533 144534
 412851 263005 149846
 533846 346871 186975
 208168 128360 79808
 944150 642016 302134
 231001 129029 101972
 322708 188527 134181
 307426 208602 98824
 309771 202421 107350
 343268 237914 105354
 398350 286819 111531
 953255 666448 286807
 328489 243295 85194
 370229 267765 102464
 507185 369694 137491
 295684 218195 77489
 807741 596350 211391
 937524 765654 171870
 237595 193260 44335
 303859 251619 52240
 392397 335795 56602
 728936 549599 179337
 468802 384362 84440
 475879 419352 56527
 1091642 784240 307402
 252655 213317 39338
 566748 489818 76930
 226777 198583 28194
 625362 496395 128967
 226411 198023 28388
 540917 480260 60657
 541760 434302 107458
 384005 317455 66550
 1896659 1715088 181571
 336053 296997 39056
 497754 401520 96234
 308828 273696 35132
 1028805 886354 142451
 441581 393487 48094
 606026 499204 106822
 882784 799190 83594
 347382 302987 44395
 860572 696960 163612
 1050334 897537 152797
 839101 751645 87456
 373441 330429 43012
 605111 513207 91904
 365077 317273 47804
 1357507 1234371 123136
 436116465 407123914 28992551
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
7516 10239 25 26
1353 1885 8 18
1265 2702 21 41
1498 3535 63 205
1226 3333 136 469
1425 4315 689 929
10503 5799 1781 2572
27393 6732 2518 4412
64762 8500 3807 7711
144591 11252 6115 13634
223762 13608 9226 21283
367319 18190 15713 35753
584999 23501 35812 61284
1001997 32648 80399 108275
1700450 43776 122129 163428
3085346 62536 188257 242957
5512156 91539 276403 335236
9154461 140432 368810 420485
13170398 218127 446032 478709
13597437 326113 511557 521503
7710123 451734 616362 610900
2337635 591992 758264 748671
1126250 750051 920486 907128
1208480 928585 1095633 1081234
1407448 1122277 1283870 1266457
1624322 1333246 1487933 1469934
1839496 1548761 1699211 1684305
2061989 1773015 1918973 1897913
2268029 1985391 2124540 2107513
2459307 2187157 2325165 2308957
2636243 2381826 2507220 2490612
2805088 2560440 2678308 2659401
2953002 2712886 2816699 2802336
3058894 2866878 2957135 2943979
3141265 2989251 3071235 3061515
3223743 3093254 3154041 3153072
3271164 3165843 3218893 3216030
3299413 3219574 3260887 3252795
3297473 3237970 3268907 3271235
3273813 3231802 3256529 3251008
3232046 3198564 3213264 3211213
3163798 3143157 3154383 3153399
3072666 3059852 3063615 3065787
2956922 2950688 2956232 2954741
2837671 2830817 2831366 2834003
2697301 2692690 2692086 2698046
2500944 2498353 2497018 2500156
2291628 2288313 2286830 2289438
2081500 2081063 2079438 2080813
1880839 1880933 1881955 1882617
1726781 1725598 1727255 1720564
1535501 1535224 1535994 1538974
1424687 1423172 1420251 1423843
1358080 1357054 1358222 1360181
1281014 1278431 1277991 1277928
1205272 1207776 1206622 1208920
1168992 1168517 1166370 1170519
1118383 1118020 1115562 1120140
1120994 1119754 1118592 1121392
1115017 1114464 1112822 1115279
1115956 1118932 1114870 1115562
1102011 1100523 1100392 1101904
1115017 1110564 1112712 1114850
1081770 1076753 1078716 1078705
1002162 1001014 1001972 1003134
865192 865307 864113 865341
702362 702160 701460 703317
565470 567789 566413 567356
460061 461571 461006 460837
307577 309394 306966 307412
140356 142694 142182 141156
28756 28598 28406 28308
17 14 19 15
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
