A = [
2219595 2598584 36144997 1093457 1089914 1057768 847862 911415 824053 648249 626250 604230 600462 592577 581921 578815 573215 574388 574816 563604 562663 561774 553157 551366 554400 661069 663707 681398 786739 789008 807689 812833 812012 816222 822902 820530 815223 812990 813128 805735 802507 809285 802169 800108 804105 794789 789144 797652 790249 785376 789851 778737 782415 778728 770455 768020 762932 766249 755862 753450 757778 753358 749872 750053 747309 750084 743330 738831 737094 731247 727496 722822 717968 713358 709766 703438 698141 693812 687884 681832 678109 675310 668941 663004 661172 653624 646501 637614 628876 625466 620414 614042 610337 604197 598848 596612 591674 586681 581225 576483 574057 567856 563567 560917 557185 552332 547136 543798 539177 533181 528482 526787 522585 519893 514481 511379 506485 501716 498770 493498 489782 487126 481707 479024 473560 470710 465330 462708 457638 453723 449585 445971 443230 439045 436022 432317 428954 425554 421414 417410 413932 410676 407959 403584 400828 397462 394006 390478 385532 382695 378102 376571 373804 369715 365099 362610 359118 354739 352361 347666 345639 344744 339882 336841 334539 330019 328296 323878 321354 317613 314974 313397 308035 306934 302597 301188 297185 295718 292352 289673 286939 283477 281768 279267 276620 273892 271412 269106 265940 265914 261596 258886 255955 254099 251707 248923 246903 243766 241838 239931 236583 235118 232452 230213 227487 225190 223603 220760 218561 216394 214936 211347 210521 207593 205441 203780 201674 199058 197877 195455 193874 191840 189722 188023 185238 183228 181733 181039 178027 176539 174654 171893 170657 168156 166906 165013 162787 161200 159475 158106 156351 154180 153087 151895 149814 148052 146073 145527 143641 141561 139868 138792 136764 135711 134163 132549 130769 129113 128080 126209 124912 123699 122462 120799 119369 117857 116768 114893 113979 112735 110923 109871 108249 107631 106311 104905 103573 102252 101144 100009 99195 97147 96589 95459 94177 92691 92218 91445 89408 88456 87656 87005 85609 84331 83328 82426 81187 80441 79669 78785 77482 76356 76013 74789 73698 72869 71818 71118 70331 69300 68451 67836 66830 65858 64810 64418 63399 62519 62051 61651 60527 59727 58963 58103 57437 56858 55975 54981 54570 54160 53209 52451 51971 51263 50645 50309 49312 48785 48374 47693 47144 46199 46146 44973 44593 44140 42887 42768 42298 41605 40978 40639 39873 39789 39289 38731 38400 37275 37071 36557 36214 35697 35322 34906 34169 33987 33639 32645 32534 32071 31508 31446 31112 30400 30228 29858 29386 29064 28623 28007 27898 27483 27106 26426 26415 25918 25357 25280 25179 24655 23973 24028 23790 23417 23083 22622 22575 21937 21734 21417 21504 20854 20598 20209 20124 19729 19611 19409 18965 18932 18597 18434 18271 17642 17511 17266 17171 16733 16640 16401 16268 16064 15634 15566 15423 15000 14872 14559 14423 14162 14267 13865 13697 13433 13634 13080 12978 12585 12796 12437 12185 11864 12100 11815 11506 11638 11341 11230 10933 10733 10737 10686 10334 10455 10299 10157 9966 9823 9758 9382 9338 9061 9096 8962 8640 8591 8585 8436 8385 8347 8148 7985 7861 7967 7649 7642 7512 7340 7245 7279 7005 6925 6786 6788 6882 6556 6646 6474 6303 6270 6261 6118 5990 5896 5934 5856 5603 5758 5554 5545 5355 5365 5251 5191 5019 4978 4910 4891 4690 4868 4820 4638 4499 4525 4463 4480 4519 4224 4272 4128 4124 4058 3972 4061 3966 3813 3746 3752 3711 3483 3613 3563 3543 3426 3513 3364 3361 3280 3184 3224 3188 3155 3077 3035 3057 3008 2874 2999 2841 2834 2891 2722 2742 2740 2645 2597 2594 2517 2533 2537 2496 2461 2403 2376 2310 2403 2284 2272 2183 2234 2146 2041 2069 2082 2009 1989 2054 2003 2016 2019 1978 1903 1952 1850 1887 1783 1788 1794 1794 1748 1750 1662 1688 1774 1680 1628 1653 1565 1569 1438 1521 1558 1539 1529 1459 1462 1472 1543 1481 1440 1371 1343 1435 1334 1290 1395 1330 1239 1331 1265 1274 1303 1232 1247 1197 1218 1219 1212 1177 1127 1203 1163 1129 1159 1137 1030 1087 1045 1061 1038 991 1086 1037 1063 968 1012 1039 994 1049 1016 917 927 1011 950 965 960 961 883 893 954 889 918 848 873 852 895 833 832 838 804 842 843 795 826 807 819 748 768 769 758 796 809 739 727 709 679 739 709 774 700 743 681 678 664 677 665 663 650 631 649 608 614 657 677 667 623 680 660 611 684 607 609 648 574 609 596 579 570 567 586 573 557 622 587 580 521 571 557 572 549 522 551 525 544 578 532 528 564 524 535 509 520 510 522 504 538 533 482 503 510 492 485 463 480 488 484 492 428 431 452 471 463 424 444 409 444 440 413 446 399 436 421 411 438 408 466 428 407 420 417 397 412 422 406 402 406 380 408 374 401 408 410 404 437 442 407 370 373 342 386 405 367 357 355 388 371 386 365 357 374 356 356 393 371 363 386 329 360 310 327 385 346 359 318 356 340 332 389 356 322 323 315 337 334 296 316 299 337 296 297 314 295 300 279 288 302 304 285 264 309 303 278 297 297 289 321 264 262 298 292 267 309 258 306 299 270 262 264 290 281 247 293 254 248 295 260 244 293 258 252 261 235 269 254 270 253 253 247 251 242 246 254 260 237 236 249 260 226 213 229 247 244 230 229 250 228 257 242 225 198 197 237 233 228 231 213 211 200 224 244 201 237 212 216 231 203 221 201 238 202 210 204 222 186 235 208 204 193 199 192 202 233 198 185 221 212 195 216 200 208 209 197 218 198 203 185 211 206 197 181 188 184 215 181 195 203 189 190 190 164 188 184 144 188 201 162 184 190 179 171 179 179 164 151 184 167 162 150 153 153 173 156 159 150 167 166 172 164 142 173 170 150 163 177 151 156 148 159 146 155 147 141 136 155 134 129 140 130 135 150 136 136 128 147 126 127 125 147 133 166 118 144 142 120 148 131 140 121 126 128 126 117 131 135 127 127 134 120 116 125 132 118 147 110 111 122 126 105 127 132 110 132 141 128 113 135 117 106 104 110 125 127 111 125 104 103 122 112 105 100 126 109 107 108 126 102 119 105 109 91 111 110 99 105 81 104 85 109 109 82 80 100 89 114 87 97 100 117 106 88 83 100 107 87 97 89 96 113 86 99 98 95 103 118 92 99 92 88 87 88 95 92 95 77 83 79 87 92 77 78 99 74 83 94 75 71 82 84 71 79 83 81 80 69 98 73 76 82 79 83 68 68 75 72 121 107 100 111 105 120 118 101 102 107 102 100 97 74 98 72 52 76 83 84 66 68 59 63 61 68 85 67 66 63 67 78 63 64 72 66 62 67 65 61 69 78 70 70 65 75 77 65 56 54 54 67 73 62 60 63 60 63 50 52 55 55 56 54 54 56 45 68 62 44 61 58 75 79 50 63 66 56 58 52 61 56 55 52 49 48 53 48 65 69 57 46 40 44 62 44 46 67 61 51 50 53 52 56 44 59 52 63 54 55 55 45 52 37 91 62 55 62 56 36 44 55 35 31 49 50 40 49 39 54 39 40 50 48 55 37 55 44 41 41 36 50 35 52 35 32 35 45 46 34 45 39 25 43 41 44 37 38 38 46 50 35 35 25 34 37 34 44 43 42 30 38 42 36 28 30 43 54 49 34 38 37 31 43 29 25 35 30 29 40 27 43 36 38 39 45 28 29 44 32 23 36 38 44 33 39 25 32 38 29 35 26 31 29 34 39 32 29 27 28 34 36 28 40 28 19 37 27 22 24 30 28 27 33 30 24 32 23 32 30 46 34 33 25 29 30 23 22 28 25 20 31 29 24 21 17 31 31 27 23 26 18 22 25 35 27 20 30 26 25 29 30 24 20 28 20 25 26 22 23 21 19 23 27 17 24 21 23 19 22 14 22 23 11 21 26 32 22 27 21 29 21 22 23 22 22 13 17 20 22 26 22 15 22 18 30 20 22 22 19 15 21 23 30 20 19 30 30 37 26 23 22 26 22 21 24 16 20 22 22 19 14 22 23 19 23 21 22 23 25 18 19 24 18 27 26 19 16 11 21 23 18 25 29 24 19 20 27 22 26 29 19 16 19 18 24 17 15 17 23 15 15 23 29 26 23 20 12 17 10 17 16 16 24 14 10 17 18 21 15 20 16 18 16 15 12 14 15 13 8 15 12 13 18 19 19 23 12 21 17 16 12 20 19 15 15 11 18 9 16 13 16 22 12 21 9 14 12 9 11 11 24 15 12 8 16 7 12 9 14 13 17 9 12 11 12 17 22 12 14 13 22 13 12 10 8 17 16 12 9 11 12 15 17 14 8 17 11 14 16 12 15 14 9 15 13 13 10 10 11 10 11 10 15 14 6 16 13 10 9 17 14 13 13 12 8 8 12 11 11 11 7 16 16 13 6 7 10 19 10 14 15 5 8 8 3 8 12 13 8 5 14 7 8 8 5 7 11 12 15 12 15 14 11 7 12 14 7 10 8 10 7 12 7 16 12 10 10 5 11 13 7 11 9 10 6 8 6 10 5 8 12 7 9 6 7 7 7 8 3 7 11 6 9 8 6 7 13 10 7 7 12 11 12 13 10 14 10 11 7 6 5 6 8 12 7 9 13 6 9 5 8 5 14 5 11 8 9 9 4 5 8 8 4 6 10 9 12 10 8 7 3 7 7 9 8 6 9 9 9 6 10 5 2 4 12 3 9 7 7 3 4 11 7 4 10 7 13 3 4 8 4 7 2 5 4 12 15 2 4 4 10 5 7 5 8 4 9 11 5 10 7 8 8 9 4 5 7 6 9 3 7 7 10 8 8 5 6 5 8 5 3 7 10 5 9 3 8 12 6 8 9 7 8 4 5 3 5 4 6 6 1 3 5 5 6 12 2 9 3 6 10 9 8 4 4 8 5 6 11 4 8 0 8 9 5 2 7 3 3 7 3 5 5 8 8 8 9 5 9 8 7 7 6 10 11 9 9 9 3 11 7 9 6 2 7 3 4 5 5 3 7 6 7 3 1 2 5 5 5 1 6 4 2 4 3 5 5 2 3 8 5 4 5 2 3 2 4 5 6 3 4 4 6 6 6 3 4 4 5 2 2 3 10 1 6 4 4 13 3 3 3 4 6 2 3 
];
B = [
0 0 0
 870346 711371 158975
 507315 411847 95468
 939369 783281 156088
 852700 709405 143295
 552800 459453 93347
 925480 782656 142824
 953644 806732 146912
 497803 420714 77089
 1186209 1011871 174338
 1182249 996097 186152
 231232 195527 35705
 2147687 1813389 334298
 561553 482615 78938
 145437 124060 21377
 1159957 1011489 148468
 382516 331114 51402
 63271 54504 8767
 1296278 1133356 162922
 59748 50481 9267
 64175 55825 8350
 14604 12744 1860
 148 133 15
 17577 15593 1984
 2099064 1834710 264354
 79365 68227 11138
 117813 104382 13431
 2197023 1926341 270682
 96999 86213 10786
 200412 178481 21931
 2922737 2541209 381528
 196998 176750 20248
 331096 298428 32668
 2458385 2179023 279362
 621114 562885 58229
 929622 845481 84141
 3393033 3036203 356830
 1423727 1285863 137864
 838757 762305 76452
 4121366 3710757 410609
 853539 771376 82163
 163565 147543 16022
 5397936 4886067 511869
 85323 76623 8700
 137903 123355 14548
 9230781 8421834 808947
 153661 138795 14866
 518470 459170 59300
 14849630 13631313 1218317
 499088 450479 48609
 4 4 0
 25429401 23392904 2036497
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
209 642 1 1
23 91 0 0
71 103 0 1
94 130 0 0
63 141 1 1
86 133 871 45
2055 182 2347 227
24979 193 3151 590
112621 252 4167 843
354313 270 5657 1432
746459 327 6865 1941
1508012 433 8868 3050
2632966 652 10131 4111
4382111 1187 12431 5826
6390215 1887 14409 7756
8664553 3156 16265 10497
10158921 4850 18389 13621
10165545 7326 20421 17802
8137167 10597 24218 23200
4650285 14840 29396 29211
1673901 19873 35557 35533
315219 26390 42673 42617
64788 36073 50184 49930
59885 46834 58176 58229
67713 58786 67569 67981
76847 71333 77036 78001
87421 84282 88308 88695
97738 98277 99564 100097
108201 110041 110570 111801
119600 121227 121084 122588
128830 133023 131315 132217
137846 140454 139236 139996
142835 147848 145379 147093
147356 153476 150400 151135
149471 156356 152621 152951
150868 156431 153045 153676
148973 155181 151399 152493
147473 151328 149190 149287
144895 148052 146745 147436
143832 146464 144330 144789
142252 145178 144087 143347
143693 144569 144595 145279
146043 147090 146272 147242
149420 150890 150420 150596
155341 155493 154615 155679
160729 160897 160711 161705
165063 166787 165561 165676
169681 169516 169195 170041
171370 172924 171513 172873
172565 172648 171037 172403
167984 169603 169087 169379
162519 164571 162677 163281
153487 156284 154034 155003
143557 146344 145210 145836
133257 135410 134003 134425
120915 123691 122416 122178
109139 112190 110319 110527
98841 100772 99618 99705
90054 90930 89871 90235
80895 81619 81486 82093
75557 76382 75410 76069
71355 71906 71954 71418
65576 65984 65829 65878
61883 62427 62287 62408
59486 59634 59280 59851
58432 58676 58659 58784
58240 58477 58331 57698
59274 58803 58913 58896
58482 58317 58386 58333
57204 56946 56922 57050
55479 55372 55430 55502
53844 53593 53395 54063
51222 51728 50950 51438
47820 47840 48223 48091
42570 42924 42855 42941
38235 38228 38490 38084
31653 31849 31709 31719
23735 23773 23547 23735
19025 19020 18838 19199
14169 13977 13787 13973
8253 8233 8211 8117
4685 4777 4841 4821
223 247 244 233
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
