A = [
6408851 5991171 11899717 6472219 6248076 6014760 5709488 6161261 5933782 5937120 6318722 6611135 7405636 8047838 8525665 9165465 9762342 10673513 10979062 10706352 11248274 11557521 11301939 11285115 11467426 13811968 13943621 14109345 16121761 13581701 13832131 13725235 11346713 11565691 11586382 11551751 11402376 11170697 11090671 11040281 10968909 10961513 11053825 11135038 11068171 10923186 10778659 10797974 10494923 10408501 10444715 10151413 10324284 10339193 10177245 10093455 10041194 10024650 9704830 9476520 9551128 9342984 9323966 9317600 9202080 9263600 9107772 8941806 8870322 8676841 8587366 8501544 8372295 8356851 8354763 8267713 8184050 8138293 7978458 7781993 7652622 7538771 7403013 7299326 7273031 7143730 7018994 6803192 6662319 6573587 6452954 6333923 6271645 6178945 6105561 6070993 6006886 5944704 5873774 5779966 5707901 5608608 5523234 5471489 5406789 5354011 5301367 5249021 5191072 5133493 5053345 5015824 4944534 4890614 4864042 4824775 5458773 5484435 5449031 6070768 6085522 6034974 5978669 5908467 5852832 5797714 5742330 5697546 5643703 5578436 5518056 5432546 5350859 5289451 5215204 5156628 5104402 5061138 5013532 4956734 4903304 4843285 4772803 4696286 4627104 4567272 4523050 4473457 4420281 4395363 4330160 4277032 4223307 4150604 4090929 4034347 3981311 3937165 3895373 3846328 3811129 3760703 3709089 3659427 3600872 3547078 3509761 3457851 3416874 3381647 3333575 3300352 3257808 3215230 3171108 3125744 3086379 3045441 3010479 2969575 2937628 2902106 2872477 2832554 2795582 2760159 2712800 2678688 2653912 2634892 2596332 2560262 2530239 2502639 2467166 2434994 2400230 2368334 2336648 2306419 2285730 2260244 2229341 2207231 2178464 2149618 2124989 2086787 2060015 2039246 2003681 1973090 1953798 1926310 1902789 1878504 1853038 1829314 1802369 1779583 1751487 1723345 1699916 1680175 1649975 1625262 1601243 1574565 1546194 1522581 1498109 1476644 1453846 1431294 1409935 1389356 1368369 1350593 1330901 1311856 1292304 1271413 1255030 1236732 1217278 1200434 1181879 1165099 1147368 1129553 1115292 1095594 1080005 1063815 1046388 1033420 1017273 1004484 987113 972371 958337 942778 928764 913758 901660 888481 875628 862480 849507 838067 825207 812709 800757 788657 777384 764650 755233 741622 732072 719973 710877 699591 687596 678307 667849 658321 649040 639317 629217 620970 611695 599768 592769 584300 575342 565391 559073 549890 538971 531681 524246 516491 507614 499502 491882 484569 477231 470405 463216 456044 448525 441737 434649 429382 422731 415707 410273 402930 396812 391198 384209 379629 373270 367793 361839 355791 350792 344005 340362 336383 330050 324921 319038 315218 311051 305357 300047 295933 292101 287568 283016 279491 274383 269644 265296 262406 258194 254201 248801 246289 241917 238415 235731 232790 227615 224430 220789 217502 214991 209652 207527 204514 201295 198433 196084 192812 188983 186289 184245 180835 178324 175033 171079 168831 166682 164528 161092 158585 156837 154077 150672 149124 146203 144328 141790 139908 137939 135519 133413 130788 128986 127263 125051 123017 121493 119885 117125 115696 113850 112413 109889 108972 106706 105119 103197 102273 100924 98581 97577 95212 94395 93699 91395 90022 88747 87281 85855 84960 83702 82566 80646 80077 78315 77118 76077 75148 74154 73050 71491 70747 69635 68115 67230 65995 65350 64224 63546 62112 61179 59954 59160 58096 57595 56606 55481 54918 54099 53589 52223 51441 50252 50055 49536 48452 47603 46755 46335 45375 44894 43936 43665 42990 41888 41296 40884 40024 40063 39085 38279 37759 37348 36722 36120 35468 35064 34566 33954 33408 32989 32501 31889 31848 31120 30518 30458 29616 29168 28769 28077 27791 27341 27217 26689 26170 26038 25665 25266 24879 24502 24200 23463 23010 23252 22711 22390 21668 21585 21608 21074 20630 20288 19999 19880 19588 19169 18857 18609 18260 17921 18102 17613 17255 16923 16816 16655 16443 16019 15738 15688 15173 15159 15008 14620 14443 14263 14006 13712 13672 13505 13470 13046 12986 12779 12654 12373 12191 12101 11828 11686 11392 11156 11071 10969 10916 10583 10404 10393 10476 10102 10125 9760 9770 9596 9443 9458 9196 9025 8978 8942 8917 8562 8448 8313 8265 8208 8183 7980 7805 7873 7829 7573 7528 7237 7238 7250 6939 6977 6803 6845 6810 6804 6493 6540 6673 6297 6322 6350 6017 6091 6030 5820 5766 5751 5610 5519 5537 5428 5283 5288 5151 5222 5207 5024 4946 4965 4888 4805 4740 4676 4604 4635 4507 4491 4460 4340 4378 4357 4272 4276 4143 4130 4048 4000 4040 3904 3967 3850 3695 3761 3692 3631 3521 3684 3662 3594 3428 3476 3323 3461 3355 3288 3300 3245 3277 3306 3268 3050 3097 3088 3085 3000 2919 3113 2968 2804 2940 2777 2703 2819 2779 2703 2717 2711 2700 2636 2609 2584 2598 2567 2476 2438 2477 2459 2456 2385 2370 2371 2332 2263 2328 2327 2288 2280 2267 2264 2232 2266 2189 2125 2219 2117 2074 2010 2066 2141 2090 1946 2020 1948 1959 2045 1981 1950 1922 1875 1956 1953 1880 1869 1874 1752 1801 1820 1743 1831 1917 1761 1694 1757 1694 1715 1705 1763 1641 1656 1658 1643 1540 1648 1683 1572 1570 1577 1489 1539 1532 1502 1479 1496 1495 1566 1452 1439 1373 1392 1431 1336 1364 1447 1386 1404 1431 1271 1334 1433 1277 1342 1286 1278 1312 1263 1205 1285 1209 1252 1242 1207 1192 1246 1178 1222 1195 1154 1201 1128 1119 1110 1216 1111 1171 1208 1141 1109 1099 1136 1047 1120 1126 1082 1055 1070 1066 1074 1046 1046 1108 1063 1067 1063 1085 1035 963 1043 1014 1000 999 1024 1017 1061 1025 923 962 1067 948 1002 1030 993 883 923 1015 935 999 933 942 970 915 935 915 913 842 873 860 790 878 845 842 860 854 905 916 810 888 887 887 896 881 912 815 827 840 808 832 774 784 788 782 792 777 770 714 748 751 729 764 758 746 718 758 747 736 709 720 703 726 675 734 738 755 661 650 640 684 728 669 707 635 663 665 638 651 629 626 651 674 664 618 655 618 650 593 541 624 621 622 604 640 655 597 571 634 635 591 630 589 570 581 605 543 596 592 578 577 584 573 527 576 532 572 539 538 547 591 545 547 566 540 493 502 506 490 538 504 512 532 533 550 493 520 512 447 454 485 487 443 458 424 462 463 438 444 450 467 464 483 467 437 443 433 421 402 456 419 441 444 452 432 420 415 441 412 411 436 407 428 400 412 419 417 404 388 434 403 381 367 424 417 391 410 391 422 389 395 414 362 370 373 405 433 420 364 403 361 389 386 388 386 376 439 331 379 353 382 355 346 385 379 380 384 362 364 390 328 374 333 358 374 376 394 367 378 439 450 532 627 819 897 1004 1093 1040 1144 1070 1157 1165 1144 1282 939 742 755 795 859 809 800 770 774 757 782 742 764 735 779 768 769 769 799 801 782 750 710 707 775 765 747 779 719 709 674 733 739 738 744 757 779 783 836 865 1078 942 944 958 969 964 971 988 957 1166 2453 1216 1003 899 888 731 746 796 662 591 591 571 549 597 555 529 573 625 505 489 502 487 486 473 453 428 464 463 421 446 444 505 437 440 446 428 500 491 472 494 592 603 672 775 2258 1949 2026 1243 1046 962 909 830 740 600 513 447 444 481 544 459 518 447 429 443 391 314 348 416 566 2996 358 280 263 296 241 245 259 238 216 223 212 215 220 227 189 233 209 202 229 224 246 218 242 245 234 212 260 254 251 239 270 277 291 274 298 279 297 331 317 293 290 346 316 277 330 289 303 348 323 309 311 343 334 335 332 375 328 346 388 354 405 392 409 394 373 392 391 399 406 506 432 420 403 467 422 444 398 443 419 417 447 454 427 476 445 482 463 497 489 435 478 465 471 488 491 483 456 452 538 550 556 543 565 505 511 521 562 536 491 507 537 509 514 477 531 547 529 581 544 547 579 562 594 524 552 630 627 592 544 522 595 568 549 536 491 506 561 543 517 477 433 390 334 297 312 359 283 348 380 390 614 401 629 1118 420 357 321 275 244 241 285 238 248 248 291 228 256 241 239 249 259 240 232 232 317 276 268 266 213 235 235 231 278 298 287 292 284 264 330 323 336 277 311 317 322 298 287 290 268 244 259 278 253 258 270 261 260 257 268 255 241 270 299 286 289 299 297 270 304 283 336 313 292 271 257 222 239 227 201 205 171 186 207 633 251 226 176 187 180 157 146 151 169 172 152 134 166 150 132 154 155 150 145 114 128 126 129 123 131 126 121 108 112 123 104 91 117 120 96 117 119 83 121 101 104 108 119 95 124 83 130 96 116 117 106 112 102 98 107 98 97 92 82 110 100 110 111 100 122 97 115 105 109 111 124 107 116 103 93 101 88 87 87 81 96 88 75 90 70 83 68 77 90 75 83 93 90 80 88 64 111 104 107 103 92 93 91 93 104 99 111 100 91 98 100 92 92 103 103 87 94 104 96 125 102 92 102 101 121 103 115 95 91 121 113 118 116 110 111 134 127 127 104 135 125 139 132 137 103 149 157 134 132 143 148 137 145 114 153 155 145 140 128 149 130 150 137 134 162 149 138 117 114 143 123 126 113 107 96 118 130 119 120 120 129 119 112 106 111 104 93 102 116 109 97 100 117 120 119 109 87 113 88 100 111 115 76 99 97 78 108 110 107 100 102 109 96 83 122 106 112 97 90 120 116 83 83 117 68 80 61 73 84 63 79 55 57 49 44 45 57 44 56 50 45 39 46 40 46 44 55 61 45 47 46 55 45 48 48 39 38 40 37 44 51 35 46 28 44 36 48 38 34 42 35 48 36 41 51 41 32 35 29 39 37 44 60 42 41 34 46 48 30 36 31 39 40 40 38 35 37 36 32 26 44 39 32 34 37 36 41 49 30 34 45 48 49 32 31 32 37 35 33 36 35 36 31 24 23 33 33 20 29 30 26 33 25 25 25 27 19 29 27 31 26 29 18 21 22 26 25 22 26 25 21 30 27 37 25 26 27 32 29 23 34 18 25 21 26 29 22 25 26 27 23 24 31 28 25 27 17 29 19 30 24 22 21 26 22 25 25 31 34 24 24 22 30 16 19 39 25 27 13 35 21 32 14 30 19 16 25 24 19 17 27 33 21 21 17 23 20 18 22 21 25 23 23 23 20 21 21 32 17 22 17 35 25 36 19 25 27 35 24 24 35 21 18 26 36 23 11 31 24 19 21 22 29 20 19 31 42 20 28 33 26 33 24 30 31 17 22 29 23 36 23 30 27 30 31 24 26 32 19 32 32 20 18 27 24 29 29 30 18 26 26 18 15 19 37 24 21 22 18 25 25 18 26 25 22 28 25 25 28 28 16 24 22 18 19 18 17 18 31 22 31 18 19 25 33 16 26 19 24 19 29 26 21 23 27 23 19 16 22 27 20 17 33 12 22 18 28 14 18 13 24 17 19 20 19 17 16 13 17 12 25 17 21 18 11 14 15 11 19 22 20 19 23 11 18 20 10 15 12 13 10 
];
B = [
0 0 0
 2602230 1803173 799057
 4938987 3624765 1314222
 3465317 2549296 916021
 2941594 2134425 807169
 2385319 1723533 661786
 2328181 1726542 601639
 1869224 1380886 488338
 2006587 1524111 482476
 2219787 1690752 529035
 3937158 3091218 845940
 3024885 2366026 658859
 2726620 2124569 602051
 2161923 1679484 482439
 2325530 1830633 494897
 3220752 2590552 630200
 2289935 1807067 482868
 2958225 2388894 569331
 2109719 1683325 426394
 2153048 1709960 443088
 2694511 2179147 515364
 2309266 1850978 458288
 2360850 1913836 447014
 3324249 2705997 618252
 2473348 2003846 469502
 2885441 2356424 529017
 3398063 2765299 632764
 2882600 2342024 540576
 2451487 2008778 442709
 4106755 3361241 745514
 3012717 2482135 530582
 2854357 2343852 510505
 3875015 3199065 675950
 2925690 2421290 504400
 4360561 3602777 757784
 3501519 2910616 590903
 3338501 2757690 580811
 8508746 7014330 1494416
 3840496 3208660 631836
 4468198 3727826 740372
 7829036 6487151 1341885
 4754774 3971120 783654
 6346701 5254555 1092146
 4341846 3641278 700568
 4564435 3821075 743360
 6381296 5302880 1078416
 5133387 4310389 822998
 7344224 6129596 1214628
 3908847 3280287 628560
 9088067 7652597 1435470
 5532837 4684018 848819
 7513555 6315227 1198328
 7519326 6387082 1132244
 10153496 8601379 1552117
 3149483 2635750 513733
 10005285 8479924 1525361
 4599107 3825442 773665
 2939558 2463558 476000
 4580345 3810763 769582
 2229204 1885200 344004
 514084570 457170555 56914015
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
94 240 5 1
32 39 2 1
51 37 4 4
81 73 5 8
76 80 2 7
111 107 94 6
417 136 349 46
3643 214 431 126
349539 286 735 318
2459736 366 1122 651
4571259 500 1621 1071
8371491 748 2496 1768
13870586 1109 5711 3386
22943817 2290 14624 9332
33015282 4656 23072 18581
42742886 14258 43052 39423
45365280 25551 94551 91308
37919728 53300 170087 169409
25911994 94150 262521 262112
13677321 149281 381519 384358
5532168 211317 481996 484138
1911940 298457 589726 590735
914685 430728 687799 691685
825405 586826 791278 797485
888621 782844 905077 913218
989957 992812 1037198 1039626
1107546 1213297 1176747 1181072
1240847 1423977 1333531 1336910
1383379 1614196 1489774 1498806
1520418 1792825 1640984 1652201
1636352 1936964 1769892 1778009
1729906 2042668 1869060 1880657
1810060 2123791 1950520 1960447
1851971 2160702 1985132 1997111
1873173 2162367 2004985 2013452
1884664 2147361 2002443 2011341
1872246 2098138 1973218 1977765
1871864 2058185 1951487 1961336
1869151 2022084 1933904 1944860
1865257 1994713 1921542 1930161
1870430 1969938 1914738 1919999
1881091 1965032 1916943 1927106
1912597 1978146 1938129 1948886
1954377 2005218 1976774 1984695
2020898 2062268 2036769 2047541
2113334 2143693 2120549 2130929
2223509 2253372 2231560 2244572
2346906 2370435 2353762 2366404
2484799 2505462 2487219 2502969
2633624 2647610 2632087 2643937
2766164 2779866 2764467 2782781
2869824 2890473 2872592 2887791
2942884 2956524 2939711 2956602
2976824 2994970 2981395 2994888
2965451 2978517 2964152 2978192
2884355 2903456 2882790 2899074
2757471 2769462 2756299 2773602
2588197 2598473 2586205 2597813
2380329 2392765 2379744 2389259
2155740 2163717 2158631 2166578
1946544 1955546 1945903 1955075
1745634 1748484 1742442 1753101
1546117 1550328 1543352 1551249
1371972 1376613 1372187 1377024
1258557 1259649 1258423 1263669
1195488 1199299 1195077 1201478
1185286 1186585 1184287 1188347
1126587 1133103 1125261 1132766
1085001 1085727 1083976 1088176
1086644 1087105 1082916 1090565
1054306 1054280 1053059 1057559
1005677 1004916 1004998 1010081
916780 917957 915113 921029
806848 806290 803779 809447
694537 696667 692533 697182
568470 568171 566675 568653
412092 413357 413435 415691
289814 290029 289986 290308
225472 224993 223779 226305
151834 151679 150601 151578
80554 80843 80851 80965
35116 35062 34742 35566
1845 1875 1780 1877
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
