A = [
1785460 1898034 41764213 1927242 1780995 1506157 1442445 1419275 1299852 1423256 1481250 1395553 1608619 1551945 1592526 1735643 1611755 1764746 1832670 1741129 1773119 1764428 1724097 1752409 1725432 1698325 1776634 1767012 1734204 1757940 1771188 1801729 1761192 1790431 1797615 1783458 1801279 1773825 1782035 1892810 1820661 1847909 1940139 1909977 1950875 1942011 1895353 1978864 1922532 1846417 1845413 1706079 1693724 1670011 1586032 1516915 1545001 1587213 1493780 1462018 1489264 1453839 1430111 1394045 1368360 1377591 1333353 1314821 1311861 1284230 1276248 1285184 1264463 1267824 1278097 1264847 1256127 1256742 1232000 1202225 1196600 1193413 1161268 1146743 1155209 1118911 1080258 1033406 1006724 1003041 983525 970980 971783 956703 944974 938695 929758 925110 913640 899357 894643 883360 871281 865131 861235 849810 843118 832465 826107 819999 814326 810394 803610 798693 792452 787098 788996 780661 771105 771625 772208 765139 759052 754035 749260 743439 735265 729543 721858 715878 709181 699696 696601 687890 682450 673798 665123 663272 657036 647288 641591 637397 631692 623706 618446 612116 607624 601334 592733 584474 578758 574575 569422 558522 555525 547518 543298 536726 529279 522821 515640 511419 503418 499461 493133 487709 482707 476408 472633 466565 460998 458109 453948 449042 451629 442838 434415 430673 422242 416947 412953 407231 405930 399363 397881 392024 387924 386034 382822 377083 376366 369527 367957 362646 358276 355948 351108 349560 344012 340682 339033 336678 334003 332244 329144 325901 322901 317331 312823 306013 301785 295740 292650 288086 289701 284159 281670 280869 277830 275407 273560 267825 265986 259796 253480 246944 239919 234880 227341 221679 217003 214488 211108 204536 203430 199146 197343 194323 190808 187791 185865 183188 180285 177348 175536 172151 169704 166872 164085 162384 158692 156503 154934 151666 149839 147621 146326 143195 139956 138718 136800 134910 132999 130588 128148 127166 125146 123819 121924 120522 118098 116343 115472 112765 110971 109764 107879 106449 105803 103439 101974 100106 98341 96957 95812 94364 93899 92224 90367 89900 88277 87045 85491 84759 83121 82109 81374 79502 78358 77309 76208 74542 73831 72122 71277 70402 69505 68488 67921 66371 65460 64251 63494 62999 61901 60337 60109 58223 58511 56968 56215 55248 54688 53666 53248 51781 51099 50933 50291 49292 48687 47447 46779 46346 45764 45294 43910 43804 42741 42534 41449 41345 40540 39778 39308 38773 38273 37737 37186 36684 35912 35362 34587 34346 33358 33041 32787 32558 31857 31063 30903 29798 30185 29568 29308 28573 27796 27468 26716 26257 26673 25610 25359 25727 24864 24308 23815 23623 23233 22935 22328 22136 21675 21650 21183 20843 20420 20367 19845 19657 19071 18593 18673 18342 17982 17541 17560 17202 16933 16868 16105 16330 16111 15743 15603 14969 14681 14675 14405 13830 14028 13896 13662 13140 13278 12897 12584 12498 12276 12189 11939 11590 11660 11546 11101 11055 10745 10645 10486 10281 10447 10070 9663 9714 9555 9410 9175 9070 8834 9106 8489 8797 8297 8207 8634 7826 7815 7617 7637 7560 7407 7195 6998 7108 6971 6723 6699 6586 6558 6271 6184 6112 6025 6058 5947 5759 5670 5519 5473 5453 5411 5325 5200 5199 5088 5010 4799 4810 4900 4623 4497 4505 4357 4435 4217 4209 4180 4153 4013 4215 3984 3917 3802 3628 3688 3514 3536 3564 3507 3388 3360 3297 3186 3244 3036 2948 2933 2914 2907 2874 2959 2719 2743 2708 2517 2503 2486 2615 2533 2478 2388 2530 2270 2297 2323 2227 2271 2240 2191 2013 2105 1995 1989 1953 1812 1927 1768 1843 1750 1743 1678 1764 1667 1638 1597 1686 1503 1616 1459 1510 1567 1462 1405 1380 1315 1271 1319 1320 1314 1284 1209 1243 1208 1117 1164 1116 1142 1154 1045 1066 1063 1077 1027 1091 940 946 994 966 921 951 936 909 900 873 872 839 876 815 838 737 875 808 739 730 716 695 700 728 713 671 668 620 627 660 678 652 667 531 619 647 565 581 597 569 514 574 528 533 559 583 570 509 529 475 483 517 483 526 411 500 455 492 442 416 387 441 433 431 449 401 370 408 416 427 357 383 390 374 389 359 365 351 346 368 320 339 354 355 385 325 310 360 310 318 299 305 306 332 249 330 284 277 290 299 276 279 239 268 215 202 232 258 271 278 250 265 251 255 211 260 229 225 191 236 189 208 192 191 183 169 177 184 209 217 195 182 171 171 206 123 189 177 159 158 141 172 170 199 116 149 134 161 152 150 173 192 182 173 144 155 179 153 210 167 203 159 162 155 166 188 172 145 162 175 145 150 140 159 184 171 155 188 170 180 176 179 131 196 156 150 135 142 129 143 142 144 142 131 131 122 108 152 138 161 114 111 133 121 116 108 111 94 104 119 121 109 91 120 79 85 89 95 120 85 93 86 83 96 89 65 80 77 101 86 97 105 100 95 87 100 94 76 104 118 88 108 81 81 95 74 90 100 79 76 67 98 56 61 81 73 76 83 84 75 79 90 73 74 76 88 77 69 87 73 89 86 85 74 77 84 78 50 64 64 92 84 78 72 70 86 90 62 65 71 61 69 63 73 73 65 68 49 60 67 58 74 75 66 59 62 60 69 52 52 40 53 61 55 49 56 47 61 39 51 46 59 50 46 41 46 56 52 36 34 47 46 63 60 40 53 63 74 46 65 33 40 31 59 41 61 56 49 61 43 44 57 42 42 49 39 52 34 45 28 36 38 40 32 45 46 29 28 45 27 54 30 50 43 34 28 43 54 47 34 49 38 58 40 40 42 41 51 33 38 32 32 58 44 38 47 38 41 44 50 43 38 45 38 31 50 23 28 48 41 43 50 50 50 40 31 38 31 45 40 37 41 50 43 43 32 45 53 38 52 47 58 52 49 30 32 41 42 36 21 37 39 29 43 31 35 42 45 30 34 33 32 32 24 33 36 26 18 41 28 26 34 31 23 24 25 33 29 24 26 23 40 43 30 26 31 35 28 14 36 50 56 60 76 57 92 89 86 95 115 103 85 77 73 112 123 88 80 96 95 83 84 87 98 90 105 89 83 95 101 101 107 115 113 86 125 124 112 92 101 106 89 126 112 100 122 121 115 134 119 131 196 151 187 182 156 213 204 199 153 155 7734 340 225 182 174 103 89 117 56 61 56 47 64 48 59 50 63 50 50 37 36 43 47 37 55 39 26 39 36 41 34 42 41 44 38 35 36 21 27 37 21 43 63 40 45 44 39 72 60 57 66 64 60 39 28 20 17 15 27 32 21 20 18 18 15 47 13 22 19 80 21 19 28 18 18 27 25 14 17 24 19 17 22 17 19 18 12 23 30 20 19 30 27 31 27 23 31 33 29 37 16 34 34 32 26 29 32 35 32 50 38 24 44 53 48 24 44 30 22 50 41 28 47 43 66 57 29 50 23 25 48 47 43 46 45 48 38 47 48 42 42 38 30 44 54 34 56 52 42 52 47 44 63 45 41 45 55 39 42 50 33 30 43 38 45 37 44 53 33 54 33 42 21 33 41 30 31 40 44 54 43 40 49 49 41 39 51 39 45 38 63 60 70 54 72 48 51 55 56 48 60 38 49 56 53 55 60 72 64 59 35 44 21 22 12 40 20 9 16 13 15 18 11 14 33 15 18 12 11 14 12 6 9 14 8 6 5 10 18 23 23 9 9 10 18 9 14 18 25 9 11 8 2 12 14 10 8 12 10 18 15 26 18 22 40 29 19 21 22 11 10 15 21 15 22 15 8 14 7 13 12 20 10 18 21 34 32 38 87 26 27 18 15 25 26 22 40 28 40 121 37 24 20 35 30 27 13 18 18 27 18 21 15 27 34 34 18 11 21 19 16 14 14 19 20 24 16 10 16 22 32 21 19 11 36 34 13 25 20 15 23 14 11 17 34 30 23 24 14 21 23 25 30 30 38 35 15 26 26 51 34 29 23 25 27 25 27 38 22 32 24 30 40 24 15 63 29 27 21 26 32 32 21 28 34 35 31 29 37 38 23 42 35 23 30 25 20 31 22 47 34 29 29 27 43 39 43 37 28 49 30 23 12 30 34 31 37 8 9 13 7 11 11 12 6 11 37 46 21 42 27 33 44 55 49 43 49 30 41 43 76 30 46 60 65 44 47 52 45 77 64 33 50 59 48 55 56 43 82 105 64 86 51 43 49 70 74 43 59 65 72 48 43 68 70 74 60 29 10 19 23 12 18 16 27 17 19 16 10 24 12 14 26 26 21 20 25 19 32 13 28 22 22 36 19 12 32 20 22 10 17 26 16 31 15 13 24 17 10 12 25 20 19 26 23 12 12 7 16 16 19 9 15 17 13 10 32 8 15 11 21 6 17 12 13 13 9 7 16 7 10 10 16 12 8 13 8 6 8 15 11 8 6 5 12 7 10 5 8 6 3 2 2 2 3 12 6 5 5 10 11 17 12 10 13 3 13 8 12 8 10 9 13 8 17 8 8 7 9 10 14 11 7 12 10 12 5 7 12 2 10 11 7 16 7 21 23 11 19 20 15 6 8 15 16 13 15 2 16 7 5 6 18 3 9 12 6 5 6 4 5 13 9 2 7 9 14 9 7 8 7 4 3 12 6 14 11 7 11 14 11 5 9 8 9 11 5 8 9 6 2 7 9 13 6 12 8 10 8 10 4 12 9 10 8 10 2 4 6 4 3 2 6 5 5 5 4 4 1 8 2 1 5 0 5 1 2 2 6 3 4 10 2 1 4 6 5 1 2 1 2 3 3 8 4 5 5 2 4 6 3 0 4 2 1 7 4 7 1 8 8 9 7 9 6 6 6 4 8 7 7 7 7 9 9 7 9 2 10 13 9 11 7 16 16 7 26 18 16 17 8 8 10 9 18 7 13 17 15 10 17 11 10 10 9 13 11 13 11 10 11 12 12 9 4 10 10 5 5 6 7 4 8 3 6 11 7 20 7 8 10 9 6 8 14 3 12 13 16 13 11 4 12 13 8 6 5 10 3 6 8 6 22 9 9 7 13 5 4 5 5 10 3 8 6 5 13 15 12 9 10 9 3 4 5 0 5 6 5 4 5 12 6 7 4 4 1 0 7 0 5 6 7 6 6 7 9 5 14 5 11 2 7 8 6 
];
B = [
0 0 0
 644431 398658 245773
 1512114 1184227 327887
 722226 494045 228181
 558617 377713 180904
 413378 261647 151731
 304996 212205 92791
 169435 113926 55509
 292027 228565 63462
 443063 319834 123229
 1076967 886694 190273
 690823 522335 168488
 560949 410432 150517
 517275 378261 139014
 527255 398369 128886
 831884 679352 152532
 570879 434859 136020
 590052 457757 132295
 525839 398687 127152
 509210 384394 124816
 733824 592620 141204
 565908 438986 126922
 554498 427746 126752
 621895 497637 124258
 528020 408227 119793
 698952 565833 133119
 631132 508979 122153
 561866 440182 121684
 558783 440406 118377
 655591 536379 119212
 668696 541673 127023
 577049 458794 118255
 637254 520861 116393
 576848 461331 115517
 637393 522673 114720
 660061 539453 120608
 587424 474448 112976
 740708 614581 126127
 609090 498313 110777
 641484 530263 111221
 804767 678965 125802
 650628 542459 108169
 658323 542263 116060
 722001 615846 106155
 603366 499525 103841
 659090 542562 116528
 728900 626018 102882
 623898 513961 109937
 566189 465845 100344
 952611 846166 106445
 579094 478541 100553
 592969 490341 102628
 1277347 1179459 97888
 586304 486422 99882
 532704 440697 92007
 2123638 2020840 102798
 540053 446059 93994
 527296 437954 89342
 538406 446587 91819
 512879 427600 85279
 111746664 106943273 4803391
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
50 27 0 0
3 8 0 0
17 24 0 0
23 37 0 0
50 16 0 0
48 56 0 0
164 127 1 0
791 63 0 1
39265 112 1 0
436591 237 4 1
1270860 124 8 3
3234951 279 8 6
7130768 237 62 27
14359537 391 373 109
23322114 466 425 199
28586794 490 491 339
23003804 606 808 747
16518482 923 1489 1350
9970297 1291 2206 2139
4650299 1930 3009 3032
1379306 2396 3812 3922
189521 2900 4715 4732
13413 4156 5579 5597
8209 5257 6732 6686
8807 6470 7787 7586
10285 8152 9018 8905
11299 9604 9940 10112
12515 11642 11240 11118
13617 12732 12235 12470
14462 13885 13561 13600
17147 15340 14426 14225
17166 20798 15102 14991
16482 16077 15865 15990
17680 16507 16146 16355
29606 22773 16525 16171
21614 17175 16816 16584
17462 21280 16846 16650
17935 17329 16957 17644
18519 17871 17191 17283
17859 18175 17239 17704
18982 18633 18629 18193
18820 18668 18678 18609
19927 20396 21987 20766
20596 19922 20146 20233
21547 21638 21505 21330
23686 22410 21885 22008
22728 22500 22774 22625
23798 23372 23431 23676
24518 24708 24882 24494
25017 25166 24967 25358
26019 25818 26287 25935
25568 25924 25845 26136
25805 26079 26061 25870
25048 25148 25179 25320
24095 24478 24718 24183
23234 23220 23499 23349
22020 21785 22194 22041
20341 20866 20717 20825
18816 18880 19452 19714
17385 17638 18502 17991
16369 16134 16216 16351
15393 15522 15533 15504
14402 14765 15110 15291
14037 14173 13934 13849
13379 13660 14118 14102
13819 13747 13768 13709
13898 14132 14495 14402
24778 25282 17772 16900
15170 15081 15290 15766
16165 16219 16377 16339
16912 16993 17112 17101
17522 17573 18243 18765
18052 17912 18270 18218
17552 17655 18002 17660
16968 16994 17252 17399
17144 18484 16717 16758
14952 14871 15231 14889
11751 11966 12088 11742
11263 11182 11565 11277
10555 10443 10520 10496
5943 5953 6008 5996
5548 3674 3894 3857
266 253 242 231
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
