A = [
908451 861359 853142 966428 923082 877715 878666 894012 891728 862850 875141 849368 863544 869233 845828 858592 847434 848654 858253 837464 835385 838925 831586 828670 827522 826232 826799 827248 821883 815542 817171 818300 811345 813987 818481 810869 810494 811734 802806 799944 798163 800607 794189 792306 803168 790211 790240 798558 789239 785725 788801 785392 787616 783866 777011 778005 774803 775958 765077 760857 760001 752182 747866 744943 744214 742853 738882 731228 729464 720194 716639 712542 709072 706921 704399 701076 697272 694367 687811 686894 682843 678177 673808 669955 666780 661644 655753 653168 644668 641030 638667 635005 633067 628423 625059 622936 619097 615880 610744 608696 606830 601947 599959 596818 594521 591829 590194 587022 583458 581126 577550 573439 571371 569285 567332 563794 563117 558610 556200 554390 549948 547462 545798 542460 540786 535995 535365 533466 529703 527633 523145 521871 519722 518621 514681 510774 510147 508944 505116 502271 500199 497482 495174 492570 489834 487357 486231 483130 481429 478195 477107 474469 471428 468355 467456 465049 463755 460117 457872 455787 454420 452062 450519 447200 445860 443546 442623 439297 437130 434806 432695 431193 429813 426040 425383 424432 421727 419467 418173 416713 414596 413258 410937 408860 407731 406262 403776 402493 400030 399856 398278 394302 393472 393188 390297 388699 386095 384503 382400 380724 378128 377344 376808 375208 373156 371285 370644 367506 366981 365238 363217 362328 360516 359376 357704 355035 352150 352042 351256 351282 347606 346620 346017 344675 342233 341445 339894 338271 336280 334679 332710 330610 328390 327382 326527 325257 322123 321028 319113 317993 316560 316167 312861 311702 310200 308943 307648 306210 303830 302447 301400 300194 298313 296164 294794 293069 291298 289981 288768 287024 285689 284304 283111 281327 279813 279502 277800 276662 274850 272963 271677 270976 269046 267124 266808 266006 265057 263895 262838 260866 259678 258855 257404 256072 254488 253008 251954 251462 249766 249301 247326 245545 245154 243223 241886 241940 239680 239067 237947 236358 235608 235508 233169 232077 230538 230032 228207 228181 226951 225497 224533 222844 221807 220498 219720 217992 217894 216923 215252 213530 213407 211696 210471 209625 208879 207944 207088 205990 205146 203917 203180 201497 201211 199460 199047 198611 197591 195537 195353 194696 193004 192350 190945 190085 188994 188414 187555 186093 186076 184495 183551 182957 183088 180971 180202 179219 178697 177776 176996 176299 175320 174395 173741 172627 172077 170821 170282 169815 168847 167415 166155 165714 165250 164458 163667 162440 161826 161350 159724 159160 158671 157201 157343 156368 154944 155540 153291 153287 152976 151226 151518 150697 149417 148805 148138 147407 146898 145950 144777 144888 143837 142853 141750 141197 140226 139953 139383 138341 138065 136871 136278 135619 134967 133750 133362 132680 132824 131930 130350 131054 129479 129198 128103 127567 127291 126018 125741 125214 124642 124357 123217 122675 122261 121501 120954 120373 119547 119648 118421 118216 117078 116880 116354 115415 115352 114730 114453 113963 113438 112833 112112 110850 110967 109647 109371 109466 108586 108350 107865 107196 106208 105887 105007 104768 104846 103350 103261 102786 102681 101354 101760 101122 100397 99870 99638 98623 98692 98264 98034 97341 96208 96540 95944 95125 94969 94122 93965 93421 92725 92683 92016 92004 91268 91216 90387 90142 89863 89465 89647 88274 88425 87616 87427 86596 85682 86276 86082 85436 84817 84704 83729 83343 83599 82818 82842 81949 81727 81159 81611 80738 80346 79837 79321 79414 78711 78343 78469 78109 77578 76938 76456 75742 76627 75388 75610 75119 74620 74614 73619 73780 73104 72708 72055 72186 71947 71761 70678 70883 70403 69945 69731 69251 69325 68778 68252 68033 67682 67487 66969 66888 66949 66149 66208 65709 65020 64759 64678 64139 63952 63913 63340 62891 62694 62469 62003 61841 62015 61455 60949 61066 60649 60052 60218 59647 59548 59426 58970 58188 58156 57841 57956 57394 57431 57212 56555 56542 56195 56024 55344 56166 55638 54848 54345 54238 54224 53788 53472 53382 52861 53029 52506 52043 52314 52229 52248 51392 51162 51184 50833 50079 50830 49787 49660 49491 49877 49463 48514 49088 48703 48157 48479 47954 47410 47454 46922 46986 46745 46034 46539 45909 45599 45570 45446 45488 44971 44976 44814 44543 44463 43958 43861 44007 43478 43395 43116 42784 42913 42722 41966 42313 42284 41927 41375 41221 41349 41322 41214 40770 40559 40286 40336 40026 40076 39444 39258 39166 39085 39000 38642 38538 38345 38626 37980 37867 37838 37778 37608 37503 36992 36895 36656 36734 36263 36275 35853 36001 35846 35746 35152 35286 35330 35198 34800 34301 34504 34509 34299 33923 33959 34014 33706 33364 33079 33399 33362 32931 32673 32661 32415 32110 32128 32187 32406 31897 31609 31802 31206 31326 30803 30996 30607 30208 30447 30542 30400 30211 29936 29770 29744 29845 29147 29304 29100 29172 28876 28728 28580 28639 28876 28130 27959 27816 27896 27849 27640 27473 27371 27288 26751 27156 26696 26834 26668 26516 26347 26434 26045 26193 26100 25695 25898 25644 25299 25382 25317 25168 24793 24939 24586 24592 24527 24073 24317 23974 24055 24081 23919 23834 23874 23455 23673 23651 23622 23477 23091 22879 22984 22567 22401 22603 22225 22548 22329 22391 22013 22008 21960 21672 21768 21607 21717 21226 21036 21267 20783 21072 20718 20682 20748 20649 20423 20623 20529 20078 20033 20487 19831 19708 19819 19803 19639 19762 19610 19551 19486 19478 19093 19143 18996 19019 18995 18780 18606 18472 18179 18320 18245 18150 18104 18228 17847 17764 17698 17866 17678 17608 17458 17220 17366 17033 17263 17091 17151 16976 16813 16679 16597 16738 16227 16410 16364 16612 16385 16279 16011 16007 15986 15993 15831 15713 15501 15607 15621 15435 15571 15652 14997 15275 15280 15012 14949 15139 14647 14779 14779 14770 14537 14415 14580 14428 14456 14399 14253 14388 14161 13879 13903 13871 13850 14005 13478 13549 13453 13537 13615 13465 13335 13223 13384 13105 13135 13263 13239 12841 13073 12621 12783 12871 12840 12476 12539 12471 12288 12369 12301 12154 12152 12102 12128 11925 12124 11850 11920 11841 11631 11561 11831 11745 11504 11590 11322 11273 11565 11343 11370 11225 11328 11198 10961 10940 11110 11010 10592 10945 10663 10885 10575 10662 10661 10757 10500 10619 10667 10308 10168 10342 10365 10152 10152 10152 10008 10148 10087 9995 10133 9788 9816 9695 9759 9859 9624 9538 9841 9549 9542 9355 9257 9426 9286 9281 9179 9291 9128 9277 9213 9004 8920 9006 9015 8882 8930 8907 8726 8656 8681 8603 8700 8614 8432 8481 8394 8367 8294 8366 8177 8341 8177 8192 8182 8191 7950 7921 7944 7938 7893 7900 7865 7896 7836 7806 7756 7820 7660 7606 7732 7514 7514 7364 7411 7418 7403 7199 7302 7318 7360 7291 7082 7257 7173 7226 7220 6928 6905 6920 7032 7028 6954 6856 6804 6940 6783 6824 6749 6561 6646 6671 6601 6715 6514 6593 6538 6447 6386 6371 6377 6360 6407 6291 6187 6379 6274 6316 6167 6076 6239 6187 6121 6106 6145 6015 5873 5877 5865 5919 6068 5981 5897 5782 5775 5743 5791 5784 5869 5670 5588 5595 5541 5489 5581 5563 5554 5488 5394 5433 5408 5452 5450 5240 5396 5235 5207 5197 5278 5180 5239 5242 5167 5085 5034 4931 5198 5041 5012 4939 5012 5012 4871 4885 4821 4865 4941 4881 4834 4673 4763 4745 4647 4715 4599 4746 4684 4674 4540 4528 4546 4326 4478 4520 4450 4401 4502 4418 4410 4364 4341 4374 4339 4257 4374 4337 4280 4199 4206 4206 4333 4079 4175 4179 4131 4095 4128 4191 4086 4101 4086 4037 4005 3984 4060 4000 3931 3961 3867 3808 3803 3889 3853 3764 3753 3773 3721 3799 3768 3749 3853 3571 3693 3567 3735 3616 3773 3533 3601 3544 3599 3523 3479 3516 3433 3470 3401 3389 3356 3376 3408 3352 3394 3423 3353 3173 3368 3250 3335 3330 3267 3279 3317 3262 3180 3196 3261 3232 3284 3152 3048 3073 3070 3111 3126 3090 3125 3174 3043 2949 2950 3044 3089 2907 2939 2934 2894 2932 2894 2920 3011 2921 2835 2878 2832 2902 2785 2834 2830 2827 2843 2731 2950 2871 2821 2660 2718 2771 2766 2767 2709 2799 2606 2696 2650 2567 2657 2621 2601 2668 2635 2623 2606 2535 2538 2585 2470 2622 2588 2475 2333 2539 2478 2496 2399 2452 2434 2379 2363 2354 2376 2416 2429 2328 2315 2282 2257 2235 2314 2281 2302 2274 2270 2247 2258 2185 2229 2166 2174 2194 2198 2069 2235 2129 2152 2127 2067 2067 2119 2058 2120 2015 2107 2068 1958 2070 2018 2014 2164 1955 1964 1953 1952 1919 2019 1921 1901 2027 1922 1864 1907 1900 1927 1835 1908 1859 1836 1842 1843 1881 1764 1815 1745 1870 1820 1789 1852 1774 1812 1835 1681 1696 1773 1714 1619 1695 1676 1611 1668 1662 1671 1668 1603 1666 1643 1631 1675 1613 1709 1598 1521 1641 1605 1624 1582 1647 1674 1576 1603 1544 1508 1576 1510 1616 1483 1564 1575 1521 1486 1504 1476 1467 1477 1484 1502 1452 1430 1404 1530 1473 1417 1440 1383 1436 1396 1401 1382 1333 1359 1326 1425 1343 1324 1343 1346 1312 1323 1368 1294 1269 1381 1300 1319 1186 1266 1247 1282 1227 1295 1257 1259 1268 1223 1196 1264 1286 1187 1211 1213 1162 1261 1213 1194 1201 1206 1146 1165 1169 1142 1175 1142 1083 1129 1107 1108 1132 1090 1140 1089 1135 1105 1150 1051 1130 1129 1031 1098 1101 1093 1079 1011 1149 1074 1121 1077 1020 1027 1008 1071 1072 1044 997 1044 1050 997 1006 983 1002 1028 1034 972 923 987 981 963 964 945 957 944 988 898 957 938 933 957 945 895 969 870 917 928 922 873 880 912 932 836 892 883 838 890 939 862 889 930 881 901 894 923 863 837 863 818 799 886 833 864 778 793 796 798 828 821 855 836 780 829 779 757 759 767 811 749 758 787 774 824 800 757 723 776 768 747 708 734 771 751 725 707 749 732 707 691 736 707 727 715 746 715 688 684 720 696 688 685 644 685 698 725 671 676 649 631 670 645 655 653 654 648 615 616 608 649 636 583 613 625 634 657 646 633 681 623 602 625 632 630 591 601 562 619 585 602 584 608 614 546 562 568 555 547 556 551 582 535 546 545 552 505 533 528 547 534 530 500 509 514 540 521 500 506 484 500 513 463 503 519 470 529 493 460 521 500 506 461 499 449 412 487 402 395 435 443 490 449 444 452 444 417 474 452 455 426 493 421 473 474 439 423 444 428 479 409 415 426 452 405 472 470 394 382 433 411 448 395 414 387 420 364 382 425 412 359 423 392 403 410 427 378 372 345 389 367 366 348 378 359 398 341 373 326 340 366 403 337 350 380 317 326 330 337 336 324 302 347 328 350 292 304 326 312 326 314 320 320 300 289 329 321 320 301 313 321 313 330 298 323 316 296 334 299 334 294 317 317 302 314 307 313 299 306 278 302 313 266 274 272 270 318 254 281 290 307 316 296 278 278 263 256 292 246 289 287 269 295 278 284 288 262 261 281 269 240 291 244 284 241 262 277 273 252 241 263 274 225 233 239 266 257 249 216 237 279 243 230 240 203 232 215 246 225 221 212 232 233 233 241 239 206 228 231 235 226 224 222 223 211 193 203 219 204 219 192 203 222 224 185 189 198 215 200 232 209 215 212 216 186 216 210 231 197 182 203 198 197 196 193 210 178 205 165 205 197 200 208 195 200 180 183 204 192 181 174 179 165 176 186 195 204 202 182 181 186 172 207 194 197 180 170 186 175 176 178 171 190 171 174 156 170 149 173 153 153 167 165 164 159 149 165 169 168 144 160 165 165 170 141 153 184 178 134 166 151 148 166 140 
];
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
 193895 153142 40753
 695778 550245 145533
 653270 517660 135610
 217506 172204 45302
 1041441 824365 217076
 217932 173184 44748
 701662 556591 145071
 570741 451278 119463
 698691 554580 144111
 764281 607145 157136
 509178 403172 106006
 739121 587230 151891
 460596 365321 95275
 831671 660476 171195
 748643 596556 152087
 475250 376928 98322
 781250 622071 159179
 479681 381420 98261
 764470 609472 154998
 474529 378332 96197
 743168 592790 150378
 972508 774528 197980
 335346 270017 65329
 894416 713337 181079
 312959 250947 62012
 963760 768719 195041
 905806 722775 183031
 338985 274910 64075
 938206 749918 188288
 211373 172950 38423
 84150978 68212512 15938466
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
0 10 0 0
0 0 0 0
1 0 0 0
1 3 0 0
0 0 2 0
7 1 3 1
26 0 15 11
49 0 12 20
131 0 31 41
289 1 61 59
609 8 89 78
1361 9 124 128
3086 31 171 175
8182 89 256 239
25294 221 377 343
94556 638 602 589
389100 1547 942 1012
1573624 3381 1652 1640
3716374 6181 2817 2863
3452104 9452 5149 5223
1323072 12681 8557 8649
225466 16392 13249 13368
46900 21759 18400 18698
26207 29374 24379 24255
29343 37872 30432 30459
34870 46253 37390 36838
41401 53606 44213 44104
48946 61214 51549 51767
57279 68700 59811 60376
66018 76812 69524 69853
76203 85940 79560 79324
86933 96031 89787 90357
98476 106909 101910 102014
110708 119756 114721 114445
123672 131950 127403 127428
136612 145477 140026 140366
151078 159842 154510 154986
166189 173873 170775 170716
181408 189305 184929 184942
198029 204613 201591 201563
214912 221609 218660 218715
235874 241126 237501 237162
256628 261555 259175 258231
277507 281956 281212 281543
302719 307261 305775 306221
329966 334028 332318 332750
358837 361512 359432 360622
389578 393306 390778 391184
419659 423970 421605 422193
451405 453807 452435 451556
478079 479195 479970 479139
501893 503211 504315 503976
519845 522079 522132 521428
530490 536130 532912 533756
536338 538651 539278 538151
532159 535428 532115 533191
519200 521837 519813 519750
499549 499219 499635 499633
474965 474819 473663 474934
447931 448413 446963 447996
426106 425460 426294 426151
406530 407249 407575 407161
393522 393267 392330 392032
389815 390576 390380 390124
400399 401120 400944 402717
418942 419336 417737 420581
441516 442215 443168 444065
478021 480535 478848 480466
526233 525003 523960 525551
564636 563807 565412 564526
583151 584286 584022 584131
583843 583839 584950 584095
548005 546208 546883 546717
472249 472321 473011 472762
395254 395853 395256 396319
311312 309826 311527 310116
228748 228588 227958 227720
156911 157355 156953 156514
113226 112672 112676 113274
77641 77064 77207 77439
49066 48926 49195 49063
25990 25994 25727 25903
2263 2200 2182 2126
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
