A = [
3681834 3913401 89047792 9840111 3292600 3376068 8536415 3636290 3340893 3258417 3358108 3307582 3297862 3205346 3271514 3245034 3186166 3223686 3147129 2983777 2842136 2757485 2636388 2554951 2600239 3121476 3189559 3281283 3763556 3543477 3531700 3471748 3285250 3277215 3239517 3282192 3204017 3150255 3172063 3109864 3093999 3117847 3066745 3057176 3073701 3030293 3007285 3014595 2956049 2937763 2962199 2915080 2896185 2924640 2889847 2859431 2871037 2829220 2814385 2812466 2778003 2766896 2780762 2740812 2740008 2746697 2705695 2695580 2695166 2658937 2655635 2661771 2631050 2628053 2641618 2604133 2599168 2610274 2574696 2554907 2567901 2538012 2524138 2532015 2504372 2497008 2502691 2472873 2468456 2469550 2434431 2424448 2436445 2406526 2398225 2401718 2387007 2374474 2376746 2354931 2342928 2346917 2316083 2317301 2326429 2299147 2294287 2290735 2278840 2266730 2271832 2251188 2239228 2252070 2229767 2237162 2267053 2248085 2249659 2268244 2246385 2246944 2242824 2215171 2217190 2219442 2193972 2189961 2194260 2168949 2169633 2162403 2134478 2133039 2140614 2117765 2113364 2121696 2096444 2081584 2088140 2066801 2056700 2056132 2040041 2039294 2034084 2019377 2009110 2013604 1991779 1990682 1983622 1962500 1958880 1959364 1942364 1939133 1934771 1918082 1919507 1914906 1896606 1890850 1886140 1871054 1864207 1867214 1850889 1845443 1843882 1828069 1825835 1822664 1805420 1792902 1797562 1781429 1773175 1767833 1756294 1752394 1745947 1732745 1728294 1723363 1709796 1705388 1703585 1692267 1685781 1680445 1670528 1661091 1663232 1649734 1640514 1638088 1625790 1622850 1619690 1604962 1605482 1600422 1582154 1575336 1574147 1561879 1560047 1554432 1547018 1537799 1533737 1522984 1516605 1511477 1498647 1493802 1493693 1482458 1474654 1473483 1463335 1458690 1456918 1440167 1440321 1435925 1422616 1420466 1411717 1401351 1395248 1396457 1383518 1377584 1373571 1366133 1355059 1352522 1349894 1343765 1334781 1326041 1318587 1318360 1306978 1302239 1297072 1286495 1283132 1276642 1269591 1266131 1254908 1252149 1241378 1241180 1232014 1228467 1223253 1211329 1207052 1199729 1192689 1190005 1184249 1174357 1171391 1166781 1159649 1152962 1146289 1144158 1133911 1126183 1123029 1117296 1113917 1103639 1098119 1087479 1083919 1075176 1072726 1066472 1059434 1056855 1044812 1042935 1041222 1032068 1022714 1019626 1009410 1006772 1000576 993599 989373 983002 979797 972711 965228 957788 951261 947098 940117 935902 930641 924495 919213 913497 904782 899249 895537 888462 882078 876260 870291 866273 861065 850069 847674 836473 833348 826067 820376 814859 809761 802146 798133 791283 786276 779179 774494 769545 762353 758368 754457 745932 741548 736108 730329 722127 717173 710168 705511 701487 692635 690236 684695 677482 670740 666819 659473 654571 650972 644295 636749 634945 627293 624871 619174 612419 607523 602657 594796 588276 584883 578399 573754 569429 564596 560253 556201 551332 546921 541123 534503 531680 526173 519034 516889 514326 504248 500970 498803 491376 485728 480098 475721 474066 467278 463099 459452 456475 449300 445584 439111 435567 431816 427444 423982 417440 412428 409877 406380 400760 395411 393085 388047 383682 380078 375457 371016 366915 363035 358783 354579 349956 345705 344101 339489 334046 333274 327576 323246 320568 317268 314564 310836 306238 303905 301013 296280 292838 288823 286373 281247 278022 275359 272168 268197 265632 261423 259631 255934 253193 251683 248016 244288 241386 238470 236671 232595 230167 226562 222952 220511 218134 215685 212453 209939 207934 205340 203173 199389 197229 194370 190732 188623 186373 183825 181767 179473 175782 174853 172047 169887 167824 165637 163130 160915 159163 155974 154476 152690 150222 148681 147071 145071 142714 140438 138997 136557 135814 133557 131401 129046 128115 126732 124285 122371 119691 119853 117942 114739 114998 112650 111130 109578 108274 106736 104690 104479 101990 101312 99553 97307 97043 95903 94882 92389 90927 90008 88732 87368 85560 85064 83823 82210 81299 80058 79214 77541 76969 76404 75183 74488 72795 71914 71321 70107 69870 68395 67390 66101 64883 64281 63349 62265 61438 60629 60101 58618 58095 57457 56685 55603 54852 54091 53393 52708 51663 51263 50970 49429 49448 48727 48214 47302 46755 45736 45477 44607 43916 43182 42884 42277 41770 41371 40223 39876 39377 39473 37876 37703 37554 37077 36755 35921 35494 34758 34706 34028 33600 33404 32675 32380 31804 31692 30902 30859 30160 30223 29732 28833 28518 28504 27864 27519 27208 26906 26490 26184 26157 25411 25065 24974 24730 24241 23696 23555 23421 22915 22786 22379 22216 21894 21594 21294 21194 20815 20732 20787 20045 19898 19708 19308 19323 19029 18663 18495 18253 18230 18035 17666 17673 17427 17208 16966 16648 16563 16556 16274 15790 16062 15629 15243 15438 15297 14606 14886 14704 14513 14272 14234 13829 13597 13512 13255 13205 13278 13110 12826 12934 12757 12713 12415 12336 12114 11867 12152 11837 11453 11529 11436 11224 11089 11038 11003 11021 10631 10722 10744 10636 10585 10390 10273 10091 9915 10151 9726 9779 9947 9583 9597 9700 9495 9181 9119 8984 9030 8893 8744 8667 8614 8515 8731 8565 8349 8266 8280 8241 8317 7956 8025 7928 7750 8034 7959 8001 7819 7760 7571 7528 7342 7434 7716 7260 7202 7213 7241 7097 6834 6875 6884 6913 6707 6827 6786 6771 6593 6600 6645 6607 6477 6664 6515 6491 6546 6305 6003 6093 6126 5949 5945 6055 5958 5839 5987 5735 5749 5660 5738 5680 5621 5772 5613 5602 5664 5584 5458 5448 5537 5471 5357 5337 5180 5387 5576 5107 5100 5240 5076 5195 5165 5275 5149 4996 5143 4926 5046 4976 4734 4743 4956 4589 4748 4792 4713 4693 4715 4661 4685 4646 4615 4788 4805 4831 4492 4707 4566 4488 4388 4382 4396 4309 4487 4497 4519 4296 4399 4490 4313 4290 4286 4359 4221 4153 4224 4113 4103 4045 4045 3993 4170 4127 4142 4032 4092 3913 3977 4049 3944 4041 4089 3869 3739 4001 3812 3891 3827 3924 3741 3968 3836 3899 3761 3827 3887 3737 3698 3757 3679 3845 3755 3600 3783 3605 3779 3581 3634 3528 3640 3741 3536 3571 3564 3658 3609 3677 3441 3514 3487 3399 3477 3511 3533 3389 3466 3332 3385 3334 3372 3493 3367 3478 3346 3469 3368 3141 3117 3176 3238 3210 3132 3248 3185 3202 3146 3216 3204 3144 3129 3017 3201 2958 2975 2906 3009 2930 3076 2917 2885 2955 3028 2900 2855 2887 2962 2830 2901 2879 2854 2809 3006 2780 2811 2818 2804 2698 2778 2751 2780 2775 2750 2645 2702 2638 2621 2561 2735 2617 2618 2523 2733 2647 2587 2560 2594 2591 2628 2565 2528 2368 2435 2498 2504 2518 2537 2589 2446 2577 2490 2618 2478 2436 2460 2369 2335 2436 2325 2360 2393 2252 2299 2310 2247 2279 2267 2273 2298 2187 2182 2656 2273 2333 2391 2208 2282 2200 2302 2259 2232 2185 2203 2281 2209 2236 2256 2133 2142 2121 2147 2133 1977 2107 2171 2178 2089 1994 2161 2013 2006 2102 2020 2404 1943 1985 1937 2067 1957 1980 1877 2027 1853 1927 1888 1858 1868 1925 1896 1823 1931 1850 1796 1900 1854 1855 1830 1853 1818 1901 1855 1769 1871 1831 1819 1779 1776 1805 1791 1820 1718 1849 1791 1894 1694 1790 1875 1820 1736 1782 1762 1822 1847 1853 1696 1675 1777 1832 1733 1731 1746 1684 1600 1698 1653 1646 1666 1675 1639 1702 1910 1777 1629 1633 1652 1622 1614 1730 1612 1575 1743 1670 1569 1536 1617 1556 1576 1543 1629 1649 1642 1583 1544 1661 1623 1552 1575 1576 1621 1520 1517 1568 1510 1461 1399 1420 1414 1522 1528 1505 1509 1514 1474 1432 1394 1493 1429 1491 1405 1363 1365 1385 1463 1369 1382 1362 1332 1400 1392 1513 1468 1388 1426 1379 1392 1354 1354 1423 1461 1432 1329 1716 1394 1419 1312 1402 1396 1300 1389 1344 1306 1303 1314 1379 1429 1308 1337 1382 1381 1256 1306 1327 1302 1280 1336 1261 1275 1228 1228 1235 1297 1207 1256 1157 1154 1228 1242 1187 1152 1160 1246 1190 1238 1205 1236 1211 1191 1284 1255 1121 1152 1267 1177 1239 1282 1169 1193 1240 1146 1197 1170 1180 1181 1146 1140 1125 1227 1159 1109 1100 1079 1142 1037 1106 1143 1103 1112 1076 1066 1101 1046 1098 1068 1043 1024 1099 1072 1039 1048 1056 1027 1094 1021 1043 948 1031 1044 1065 1014 1061 999 1095 1061 987 977 966 968 999 972 936 931 952 972 994 1007 960 944 901 935 953 974 950 920 921 980 959 1004 912 889 883 847 914 869 892 929 851 856 821 806 824 829 930 899 887 807 796 823 770 755 799 738 783 801 829 773 718 790 731 894 785 711 786 745 683 755 679 700 709 847 707 685 735 717 755 684 719 775 712 724 694 727 743 720 675 766 726 714 714 749 695 699 687 688 670 710 793 694 695 690 1101 706 709 664 680 659 686 673 699 653 693 725 743 726 693 703 662 723 682 661 668 691 679 720 658 746 727 705 720 661 690 681 687 660 719 708 722 716 722 686 649 668 713 677 678 694 644 678 642 654 639 662 647 630 630 629 626 610 602 626 625 643 601 693 564 628 644 617 597 555 623 554 581 640 536 574 579 655 646 648 584 568 602 560 599 584 560 524 584 616 627 580 574 591 595 570 557 642 540 564 569 554 518 569 528 493 560 506 518 530 530 570 506 510 549 554 538 597 515 515 546 510 482 551 481 413 525 553 492 533 494 522 485 468 504 508 498 513 474 518 508 510 481 504 643 517 521 480 471 436 456 513 493 501 447 481 473 487 519 764 497 472 505 464 430 485 458 488 509 516 491 466 482 501 461 459 452 464 513 466 537 525 484 480 470 491 472 454 484 459 486 435 453 452 428 436 451 452 488 472 471 458 460 440 486 403 392 403 454 398 425 397 373 387 434 385 378 376 417 382 388 352 350 377 353 401 395 383 408 354 340 357 409 380 374 362 329 431 425 393 371 383 376 429 366 414 410 349 346 366 378 424 365 385 500 378 363 357 363 394 388 348 349 349 437 373 361 353 347 424 357 336 360 359 333 324 376 373 338 395 346 364 350 382 355 359 351 366 386 326 355 361 346 296 323 343 359 367 364 368 349 328 326 333 363 345 367 327 336 303 335 346 336 322 304 311 334 334 363 362 288 291 338 327 320 267 304 291 303 301 312 319 286 342 326 315 297 310 341 283 309 302 269 271 311 290 293 312 327 313 319 273 281 314 299 302 290 276 273 304 295 297 272 294 356 284 271 267 314 332 294 309 278 277 285 322 333 301 281 317 281 315 295 278 305 322 306 286 289 277 301 254 259 301 311 281 460 285 320 308 334 261 294 302 296 313 263 272 284 271 269 283 254 253 262 254 218 258 252 263 252 255 261 247 258 273 243 255 221 225 233 277 261 223 245 252 241 218 231 201 211 219 248 232 250 210 250 243 555 243 247 254 244 222 236 234 235 237 235 222 245 226 238 254 203 221 237 242 225 195 220 220 225 200 185 203 224 232 217 233 194 213 194 203 204 201 211 187 210 206 211 193 237 209 212 196 199 214 211 233 227 184 210 178 237 220 205 197 227 200 188 215 196 177 210 209 187 204 203 197 210 185 182 182 216 196 200 195 209 207 212 181 186 179 154 154 176 183 182 203 164 177 182 181 153 181 186 181 149 157 157 141 147 174 186 162 162 174 155 168 149 163 157 141 182 148 133 154 174 168 172 171 165 171 168 173 175 163 151 170 134 163 156 158 150 170 144 166 177 161 169 167 170 148 172 180 167 180 163 182 212 163 187 152 159 174 170 185 159 155 186 162 169 169 161 169 161 156 164 174 156 148 148 167 134 169 168 
];
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
 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 = [
7367 10087 21 25
1332 1853 6 17
1237 2656 21 37
1457 3461 62 195
1192 3277 130 450
1368 4253 677 896
10242 5687 1743 2501
26742 6591 2470 4270
63249 8340 3702 7491
141350 11046 5951 13282
218297 13377 8989 20717
357877 17888 15332 34877
568797 23147 35052 59711
973185 32104 78807 105667
1655819 43064 119788 159654
3015056 61618 184553 237371
5397331 90137 270573 327395
8961770 138343 361376 411299
12885843 215049 437761 469611
13306050 321563 503835 513277
7545380 445513 607661 602356
2289276 583707 747791 738435
1107892 739216 907698 894708
1190440 914805 1079945 1065622
1386628 1105513 1265375 1248418
1600530 1312640 1466141 1448495
1811881 1524731 1673717 1659714
2030998 1745059 1889826 1869052
2233112 1954114 2091985 2075649
2421441 2153397 2289559 2273819
2594619 2343564 2467808 2451162
2759373 2519183 2635513 2617005
2903359 2666403 2770269 2756020
3005457 2816889 2905919 2893542
3085672 2935824 3017177 3007828
3165270 3037061 3096403 3096654
3210575 3107047 3158059 3155874
3235448 3156952 3197655 3190169
3230691 3173150 3202470 3204955
3205700 3165659 3187962 3182965
3163077 3130736 3143360 3142253
3092319 3071928 3082149 3081490
2999644 2987057 2990836 2993210
2883297 2877533 2882452 2881071
2762684 2755901 2757507 2759999
2621646 2616840 2616161 2621787
2426741 2423044 2422411 2425533
2219470 2216076 2214675 2217539
2012588 2012204 2011042 2012436
1817937 1818093 1818308 1819508
1667494 1665709 1667564 1660984
1479286 1478954 1479275 1482523
1374252 1372138 1369356 1373190
1310309 1308758 1310124 1312782
1237052 1235054 1233956 1234634
1167303 1170194 1169118 1171665
1135392 1134844 1132566 1136681
1088116 1088110 1085751 1089730
1093159 1091619 1091686 1093518
1090037 1089647 1088439 1090279
1093205 1095175 1091743 1092780
1079092 1077225 1077421 1078879
1093000 1088370 1090404 1092003
1059091 1053811 1055836 1055791
981965 979652 980895 981881
846684 846107 845492 846154
684653 683631 683308 684691
551058 552277 551231 551977
446142 445621 446596 445593
294630 294785 293727 294229
131474 132352 132311 132091
26060 25715 25994 26142
2 3 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
