A = [
1053394 999644 991768 1119973 1072823 1015203 1015644 1034206 1025884 995315 1011279 978402 995905 1003170 978002 992811 974435 980688 994113 966170 961219 969585 959887 954507 954193 954606 956388 956012 953542 944635 949025 950332 940938 945601 949122 943209 943928 943523 935518 934048 930352 933029 924339 922279 936013 920722 918379 928458 921906 915619 921347 914883 916530 916867 907623 908204 901379 906281 893376 882437 883147 875096 870476 867211 865636 866896 860718 851712 849526 837064 831973 828819 824172 821422 822254 815697 811726 810076 798478 795262 790186 784424 778445 772398 770006 762333 752233 743560 732927 729425 724816 722814 719743 713154 709877 706506 702520 699027 693342 689474 686961 682011 679065 675052 674931 671120 668317 665991 661322 659155 654451 649356 648239 645524 642740 639378 638668 633149 630403 628963 624535 621055 619182 615652 613095 608475 607128 605874 601059 598172 595138 592173 589900 588365 583748 579353 578261 576612 571960 569041 567632 564298 561022 559174 555814 552365 550717 547061 545330 541959 540606 537990 534723 530819 529726 525942 524670 521033 518277 515409 515012 511262 509264 505665 504340 501663 499662 496546 494277 491375 489277 487453 485565 481865 481332 479797 477020 473844 472781 470921 467354 466651 464871 461848 460479 459564 456647 455229 451079 451584 450350 444858 444019 442312 439800 437747 434511 433117 430619 428517 426199 425078 424744 422566 420699 418980 418048 413596 414023 411577 408700 407063 405109 402972 401382 399210 395326 395644 394067 393614 389822 388802 387612 386549 383650 383129 381528 378620 376660 374872 372296 369800 367500 366852 364891 363595 359918 358962 356429 355122 353158 352869 348605 347884 346216 344757 343353 342186 339658 337939 336048 334945 332981 330312 329084 327408 325478 323994 322871 320809 318827 317298 316081 313972 311563 311236 309276 308372 306636 304337 303059 302195 300118 297974 297256 296502 295253 294090 293068 291401 289696 288707 286539 285387 283721 282330 281141 280324 278344 277770 275946 274098 273034 271178 269496 268978 266610 265943 264375 262753 261953 261834 259023 257662 256354 255780 253660 253534 252141 250412 249472 247798 246607 244898 243750 242238 242154 241146 239011 236957 237224 235530 233734 233159 231808 230808 229819 228704 227766 226529 225799 224193 223728 221794 221302 220774 219488 217536 217047 216335 214564 213581 212434 211493 210021 209598 208618 206781 207278 205220 204178 203811 203445 201352 200748 199486 198793 197637 197219 196147 195069 194085 193249 192275 191562 190166 189463 188961 187941 186515 184736 184550 183767 182768 182155 180969 179836 179456 177634 176668 176263 175061 174975 173826 172474 172851 170607 170474 169824 168394 168144 167492 166010 165250 164630 163892 163152 161826 160766 161054 159684 158837 157375 156688 155601 155361 154715 153586 153349 151911 151072 150652 149829 148663 147831 147218 147390 146357 144771 145586 143763 143676 142346 141528 141090 139903 139654 139054 138396 138001 136824 136211 135689 134899 134259 133674 132736 132773 131490 131385 130227 130021 129197 128243 128045 127489 127188 126409 125916 125310 124243 123403 123073 121815 121456 121383 120567 119922 119463 118940 117845 117310 116545 116232 116273 114809 114520 113880 113921 112494 112876 112208 111427 110706 110569 109609 109595 109105 108665 108178 106829 107078 106405 105577 105506 104658 104269 103837 102972 102995 102313 102173 101592 101292 100549 100109 99882 99326 99821 98310 98094 97521 96966 96292 95355 96160 95801 95008 94372 94129 93088 92559 92916 92046 91840 90958 90624 90163 90624 89722 89175 88676 88148 88301 87477 86971 87096 86857 86252 85491 85028 84294 84950 83682 83811 83370 82727 82725 81609 81676 81221 80646 80081 80111 79901 79738 78453 78698 78201 77723 77604 76893 77262 76510 75823 75538 75318 75024 74556 74424 74349 73490 73683 72907 72350 72238 71884 71520 71030 70954 70653 69975 69825 69498 68836 68907 69132 68513 67870 67824 67316 66640 66890 66219 66014 65936 65401 64698 64663 64440 64443 63928 63725 63454 62681 62879 62403 62213 61355 62373 61726 61039 60516 60222 60209 59831 59559 59257 58856 58803 58391 57863 58020 58019 58021 56975 56772 56936 56450 55751 56395 55229 55337 54991 55375 54924 54011 54483 54029 53660 53771 53268 52707 52694 52278 52157 51871 51251 51748 51038 50766 50864 50412 50579 50057 50030 49837 49533 49517 48793 48738 48941 48338 48218 48068 47677 47749 47484 46831 47113 47017 46721 46067 45888 46041 45962 45792 45454 45150 44845 44870 44523 44553 43866 43805 43731 43561 43405 43034 43043 42816 43218 42229 42251 42196 42229 42039 41909 41162 41231 41016 40892 40452 40489 40099 40308 39995 40009 39248 39381 39524 39205 38837 38381 38547 38460 38179 37934 37933 37913 37699 37221 36936 37182 37193 36814 36521 36425 36193 36025 35936 36000 36303 35753 35380 35643 35001 35048 34627 34701 34286 33879 34033 34257 33956 33770 33433 33258 33313 33337 32532 32593 32639 32591 32203 32050 32038 32069 32323 31393 31271 31100 31203 31136 30857 30643 30701 30437 29852 30261 29804 30045 29755 29607 29400 29432 29032 29160 29106 28634 28957 28472 28192 28344 28247 27980 27658 27720 27306 27293 27300 26845 27119 26680 26768 26708 26673 26491 26691 26181 26280 26284 26280 26249 25764 25431 25498 25186 25028 25145 24851 25107 24852 24954 24610 24469 24514 24153 24319 24020 24056 23662 23432 23621 23115 23305 23117 22963 23045 22980 22687 22827 22700 22361 22217 22696 22013 21960 21993 21968 21818 21914 21864 21727 21710 21573 21233 21274 21120 21064 21019 20870 20617 20555 20155 20292 20278 20193 20080 20251 19871 19797 19724 19850 19728 19577 19425 19079 19318 18930 19182 18965 19013 18859 18728 18543 18477 18633 18060 18307 18154 18414 18104 18088 17721 17841 17735 17737 17551 17390 17220 17328 17343 17130 17251 17338 16646 16956 16900 16625 16595 16757 16343 16504 16460 16420 16151 16105 16312 16020 16097 15982 15844 16030 15719 15513 15481 15442 15408 15576 15017 15126 14993 15039 15111 14966 14845 14664 14857 14580 14628 14747 14684 14300 14490 14127 14209 14353 14265 13888 13918 13810 13710 13738 13727 13601 13587 13457 13433 13260 13432 13157 13275 13148 12927 12928 13142 13086 12881 12955 12687 12600 12862 12691 12746 12512 12706 12451 12350 12247 12397 12235 11836 12246 11882 12060 11757 11803 11879 11915 11700 11760 11901 11462 11360 11559 11457 11299 11288 11300 11136 11275 11272 11170 11332 10853 10929 10846 10857 10965 10721 10645 10903 10496 10655 10376 10323 10496 10327 10320 10285 10270 10146 10297 10204 10009 9975 10039 10072 9844 9946 9993 9679 9640 9650 9535 9669 9604 9372 9494 9393 9334 9227 9314 9109 9284 9113 9131 9089 9059 8874 8812 8793 8844 8802 8810 8760 8774 8753 8717 8662 8726 8516 8444 8612 8401 8407 8221 8219 8287 8223 8036 8144 8202 8222 8162 7894 8055 7977 7981 8041 7756 7709 7695 7867 7849 7785 7607 7544 7733 7539 7563 7484 7311 7426 7402 7302 7441 7242 7348 7287 7114 7100 7118 7096 7052 7099 7000 6854 7091 6955 7032 6898 6731 6954 6911 6770 6784 6895 6683 6561 6593 6582 6569 6757 6648 6557 6403 6387 6381 6439 6380 6456 6327 6197 6238 6192 6147 6240 6164 6192 6133 6031 6052 6030 6077 6077 5889 5995 5847 5769 5756 5898 5784 5861 5825 5764 5618 5606 5529 5782 5626 5610 5504 5581 5595 5452 5493 5385 5435 5500 5455 5412 5235 5310 5261 5186 5208 5173 5332 5223 5242 5076 5025 5098 4828 5000 5000 4984 4886 5004 4932 4904 4874 4849 4876 4844 4740 4889 4815 4752 4714 4735 4697 4893 4589 4662 4643 4590 4546 4610 4695 4514 4585 4561 4559 4436 4426 4540 4440 4399 4403 4324 4308 4291 4320 4298 4257 4262 4230 4195 4238 4220 4193 4287 4010 4114 4033 4178 4073 4186 3938 4039 3966 4042 3953 3878 3945 3851 3919 3838 3812 3754 3797 3803 3764 3803 3822 3779 3560 3776 3677 3744 3724 3692 3675 3715 3688 3576 3572 3609 3587 3691 3543 3438 3437 3437 3485 3512 3459 3464 3526 3445 3336 3313 3398 3452 3267 3325 3307 3215 3286 3264 3280 3359 3247 3199 3223 3198 3259 3144 3165 3164 3144 3210 3109 3264 3218 3143 3000 3072 3090 3100 3089 3024 3113 2941 3059 2992 2895 2989 2948 2936 3022 2933 2916 2900 2848 2820 2911 2781 2924 2898 2788 2647 2885 2746 2811 2699 2749 2737 2668 2654 2670 2697 2737 2714 2624 2576 2582 2558 2548 2631 2590 2598 2569 2557 2551 2558 2462 2549 2494 2451 2475 2504 2361 2541 2443 2432 2399 2366 2382 2365 2332 2406 2268 2398 2331 2227 2348 2257 2251 2436 2231 2245 2204 2229 2199 2281 2169 2176 2257 2161 2135 2170 2130 2198 2112 2155 2099 2115 2102 2079 2117 2028 2064 2007 2108 2067 2026 2071 2020 2061 2079 1914 1917 2021 1959 1855 1925 1935 1859 1899 1889 1926 1930 1844 1907 1859 1883 1886 1855 1940 1810 1739 1856 1820 1870 1791 1893 1902 1811 1825 1766 1714 1792 1739 1847 1696 1786 1779 1730 1686 1730 1709 1702 1689 1679 1699 1652 1657 1593 1751 1681 1635 1640 1595 1625 1579 1569 1596 1528 1526 1521 1623 1512 1535 1521 1547 1519 1502 1531 1491 1452 1578 1476 1520 1359 1462 1421 1462 1373 1462 1417 1434 1433 1373 1381 1463 1451 1372 1403 1375 1348 1450 1365 1337 1373 1378 1348 1344 1350 1318 1328 1319 1258 1286 1242 1260 1301 1261 1298 1238 1319 1254 1304 1197 1309 1286 1195 1254 1256 1242 1247 1161 1306 1233 1286 1243 1153 1180 1162 1245 1242 1190 1153 1190 1202 1154 1153 1122 1148 1168 1189 1106 1084 1154 1120 1097 1097 1080 1099 1079 1121 1015 1070 1056 1049 1118 1072 1042 1117 1005 1063 1038 1050 1006 1015 1051 1051 949 1025 1020 976 1014 1065 987 1025 1052 999 1034 1010 1039 973 958 964 946 896 1005 934 983 902 927 916 938 952 944 977 949 909 948 897 862 872 874 972 858 882 932 899 946 916 892 868 874 899 869 827 858 890 867 828 832 865 852 823 776 857 819 847 815 865 829 804 797 837 812 836 788 753 807 803 870 777 802 757 732 801 759 769 784 767 761 722 726 706 766 754 680 720 721 724 770 743 737 783 721 709 727 742 743 693 707 664 719 687 695 688 709 716 638 669 686 660 658 665 652 706 652 660 655 644 629 640 632 658 630 648 607 646 643 640 631 616 604 602 610 611 564 601 622 559 650 569 558 615 603 597 576 598 550 501 581 497 493 502 545 566 533 528 528 530 507 550 537 544 511 562 512 551 574 510 519 549 501 550 489 496 503 532 474 569 552 483 464 517 490 527 488 504 469 495 440 453 504 474 437 527 453 489 466 497 430 440 417 467 436 435 411 451 435 487 416 431 382 417 426 464 401 413 446 392 383 404 408 405 409 364 423 396 416 355 373 397 360 399 373 383 394 366 348 385 387 377 366 383 389 388 397 356 395 382 385 410 356 404 371 388 407 368 389 376 382 374 376 345 361 385 325 339 327 356 403 326 354 351 368 372 368 344 333 334 299 369 313 341 354 330 359 345 348 337 334 324 357 355 302 375 303 334 305 320 331 324 311 296 322 318 292 296 314 326 307 302 256 307 340 296 284 305 247 290 276 296 302 279 271 285 282 299 316 306 280 299 281 286 288 275 266 288 274 243 255 270 267 264 243 255 267 283 240 250 241 269 257 345 323 351 260 288 234 266 255 294 259 235 263 335 331 309 278 303 331 337 284 343 367 346 413 323 324 311 362 338 294 373 316 365 333 339 290 312 400 264 225 226 246 224 259 244 248 232 232 244 243 220 229 213 234 215 247 193 222 204 205 184 197 224 220 209 219 197 205 217 208 177 208 203 207 214 170 196 216 207 165 196 192 187 204 204 
];
B = [
0 0 0
 354887 242668 112219
 450456 317097 133359
 412853 288551 124302
 773508 551942 221566
 222905 160303 62602
 1649638 1199366 450272
 426016 320914 105102
 161072 120490 40582
 396940 304383 92557
 118575 88540 30035
 94105 71549 22556
 70973 54495 16478
 70130 53897 16233
 487801 374751 113050
 440515 339417 101098
 145340 110281 35059
 1768055 1363960 404095
 221002 165967 55035
 531322 415378 115944
 158734 124186 34548
 609720 478689 131031
 605613 476178 129435
 168047 132440 35607
 587324 462059 125265
 180824 142830 37994
 1267827 994492 273335
 666035 524308 141727
 173834 136895 36939
 678921 535902 143019
 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
1 0 0 0
1 0 0 0
1 3 0 0
0 0 2 0
8 2 4 1
29 1 18 12
57 1 13 23
150 1 38 47
349 2 64 66
767 13 94 89
1715 13 143 144
3865 35 191 195
9973 114 288 256
30234 257 425 399
110533 731 690 670
446104 1737 1087 1154
1780368 3734 1886 1868
4171622 6816 3270 3287
3854151 10478 5747 5910
1472841 14166 9652 9725
250494 18504 14811 14952
52611 24026 20486 20852
29367 32384 27080 26925
32483 42302 33674 33736
38995 51285 41516 41026
46303 59597 49163 49215
54908 68425 57456 57852
64262 76518 66660 67276
73757 85801 77292 77695
85200 96485 88861 88711
97501 107829 100684 101274
110443 119959 114336 114526
124045 134688 128633 128465
138487 148081 142791 142811
153187 163041 157243 157352
169445 179154 173234 173543
186281 195117 191075 191187
203586 212054 207414 207184
221707 229373 225837 225859
241061 248519 244838 245440
263878 269968 266034 266123
287466 293120 290580 289595
311389 316115 314846 315200
339158 344185 342330 342918
369700 374411 371912 372519
402237 405268 402704 404391
436265 440660 437621 438318
470287 474419 472264 472916
505206 508035 506615 506184
535175 536875 537137 536986
561652 563875 564157 564621
581773 584713 583874 584125
593903 599664 596355 597525
600226 602897 603082 602339
595741 599073 594768 596644
581235 583731 581497 581606
559119 558602 559478 559705
531945 532114 530469 532045
502686 503009 501662 502660
479023 478410 478819 478734
457669 458369 459012 459227
444089 444159 442386 443265
442054 442760 442219 441955
455055 455633 455257 457068
476767 476993 475104 479086
503107 504642 504977 506017
544809 547769 545673 548118
598866 598290 596520 598549
640828 640224 641155 641194
662143 662777 662708 663437
667193 667482 668156 668359
628282 625854 626077 626807
541288 541299 542342 541872
452965 453154 452266 454151
358018 356618 358019 357331
262295 262142 261447 261458
179301 180070 179133 179028
127442 126830 126931 127525
87314 86629 86754 86984
54730 54524 54882 54734
29026 29033 28827 29020
2584 2525 2506 2429
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
