A = [
2244541 2536545 48599435 1995689 2649928 2208985 2006341 2510589 2191502 2299031 2409292 2180524 2439526 2316063 2302098 2484096 2222222 2445770 2494934 2219956 2287674 2240728 2125418 2163155 2095011 2027098 2123284 2057191 2007575 1978084 2001424 2014820 1923280 1924973 1941661 1942317 1914075 1853901 1860613 1942605 1857502 1853959 1911883 1863511 1869358 1821851 1775386 1849224 1788584 1751155 1764720 1643428 1659818 1641434 1562027 1510001 1531942 1575826 1475158 1431382 1476319 1432212 1410038 1385522 1355175 1374966 1334596 1309083 1316573 1281308 1274136 1276491 1254223 1264796 1270752 1256295 1251890 1250631 1221817 1199090 1191022 1188572 1157438 1144457 1150909 1115684 1083784 1031406 1006099 1004010 988504 975004 976584 963093 955710 951451 945288 940077 928571 917589 917293 906421 896912 892115 885439 881666 875549 867022 862628 853714 847984 845425 840582 837677 832568 828506 831197 821092 810852 812623 812860 802908 797040 795121 788852 780533 775587 767214 761404 754431 747610 738231 733139 725527 725029 715714 706242 707760 698610 687035 681877 677404 670132 664826 655431 651201 646349 637750 629337 622877 614732 608883 603485 593961 586199 580368 573942 565121 559067 552832 546635 542706 533532 528653 524104 515988 512780 505990 502439 497356 488145 486880 482511 477251 481045 470279 463970 462563 451900 447380 439824 436354 435294 428104 425588 423445 415581 413677 411674 409212 406163 400731 400055 395692 391384 387577 383260 381865 378229 373134 369776 369006 364591 360838 359806 356838 356419 352140 348525 346263 339933 334984 333908 327944 329908 327592 324818 326992 322448 319527 318820 314658 310642 306123 297155 291932 284227 276773 268574 261820 254952 250533 248433 241916 239160 236607 233370 230810 228203 226778 224777 221663 219138 216086 214032 211140 208972 206879 205117 202114 199376 197132 193627 192491 189193 187402 185013 182885 180124 178096 176320 173716 172170 169676 167924 165707 163877 162300 160259 157268 156700 154643 152643 151020 148372 147295 145377 143651 141550 139440 137434 135708 134325 132574 131796 130018 127911 126216 124670 123097 121843 120146 118402 117691 115614 114249 112565 111148 109770 108328 106938 104975 104344 103143 101507 100263 98611 97179 96356 94651 93592 92542 91066 89956 88954 87348 86371 85145 83855 82668 82028 80786 79299 78353 77903 76232 75130 74813 73510 72195 71639 70802 69597 68817 67301 66614 65578 64638 63956 63587 62472 61611 60423 59703 59224 58037 57350 56662 55465 55075 54725 53824 52636 52344 51410 50996 50421 49395 48589 48207 47367 46449 46029 45366 45010 44575 43613 43199 42453 41526 41578 40608 39980 39694 38973 38318 38235 37789 37377 36612 36287 35300 34603 33886 33783 33542 32942 32580 31876 31583 31386 30483 30110 29923 29226 29158 28144 28210 27545 27396 26985 26610 26332 25883 25503 25153 24973 24577 24606 23601 23418 23104 22749 22706 22173 21943 21589 21440 20858 20687 20519 19923 19633 19373 18961 18888 18684 18598 18141 17888 17696 17403 17111 16987 16729 16695 16029 15885 15684 15539 15122 15067 14778 14560 14470 14137 13923 13794 13630 13127 13175 13202 12887 12767 12229 12406 12156 11956 11875 11468 11592 11257 11087 11068 10927 10692 10505 10169 10304 10068 10021 9908 9535 9550 9482 9386 9251 9254 8841 8915 8728 8488 8353 8119 8005 7883 7779 7780 7550 7522 7363 7292 7168 7040 6984 6979 6784 6794 6841 6482 6319 6289 6418 6203 6085 5841 5844 5693 5668 5642 5441 5633 5568 5360 5231 5155 5113 5134 4988 4915 4804 4687 4800 4659 4614 4425 4500 4322 4350 4157 4164 4062 4030 3954 3944 3842 3877 3740 3638 3578 3724 3617 3486 3583 3330 3333 3308 3308 3214 3045 3025 3059 3011 3009 2880 2887 2779 2753 2770 2669 2637 2670 2747 2558 2460 2442 2401 2409 2347 2368 2341 2228 2242 2217 2137 2146 2054 2028 2058 2074 2046 2013 2067 1886 1940 1847 1860 1896 1715 1779 1686 1774 1717 1652 1630 1600 1618 1623 1526 1505 1458 1452 1560 1401 1479 1450 1384 1332 1376 1344 1296 1292 1226 1257 1149 1221 1202 1202 1083 1076 1128 1111 1114 1034 1051 1085 998 992 968 1009 1000 978 1009 933 894 907 957 866 921 827 871 858 829 784 808 782 850 733 785 792 680 699 716 720 746 663 704 688 671 650 599 637 655 616 631 544 590 581 591 610 541 518 514 534 528 512 546 504 511 541 525 490 491 470 446 484 446 441 450 458 431 415 398 427 392 407 401 405 389 366 426 427 331 356 379 332 360 359 318 331 325 317 323 296 337 350 295 267 303 301 289 274 288 279 274 280 298 251 264 266 285 254 256 256 235 237 262 233 241 210 227 232 239 213 230 215 206 220 216 217 215 193 184 202 174 193 195 149 168 153 189 187 186 154 170 194 177 154 165 161 184 146 166 153 144 156 146 119 139 157 153 154 128 114 143 141 147 129 127 113 127 132 107 120 118 122 118 116 129 115 105 111 119 124 109 102 128 114 107 118 105 121 113 87 101 89 95 108 80 83 94 103 92 100 100 88 76 73 87 93 80 90 93 76 73 88 70 78 87 78 81 74 68 67 69 65 77 56 53 73 71 59 54 69 70 80 63 55 50 54 56 57 60 63 43 66 42 68 72 58 50 57 53 51 57 45 52 49 54 61 49 41 44 39 41 50 56 48 54 44 61 50 36 51 55 33 43 33 55 41 52 49 41 45 39 32 41 34 37 50 34 41 37 34 34 42 30 41 39 48 31 30 38 26 35 37 39 35 44 42 38 35 37 35 47 34 35 38 30 33 33 35 42 37 33 31 22 26 41 35 35 32 29 34 30 36 21 35 31 20 29 27 14 27 29 31 36 30 31 41 32 25 21 26 19 22 31 23 25 27 26 17 22 27 34 21 20 14 27 18 23 13 21 23 26 16 18 27 23 20 17 20 22 12 24 20 26 30 10 25 22 18 17 14 18 14 26 20 19 20 17 19 15 17 16 12 17 12 25 12 24 20 14 16 19 26 21 12 12 15 17 15 22 27 15 15 23 18 21 21 15 19 25 21 25 12 19 27 29 37 27 27 47 38 36 25 23 24 32 29 39 27 42 38 45 46 49 46 35 57 48 47 52 62 58 48 48 52 62 51 77 61 45 55 48 47 62 41 47 44 44 47 45 40 35 48 43 36 45 40 32 36 39 36 48 456 63 62 40 49 48 30 46 26 26 32 43 33 28 31 28 41 23 21 41 29 32 26 18 26 22 24 25 17 30 16 23 21 22 20 19 15 12 7 21 17 19 13 20 17 24 28 20 17 21 16 19 11 16 10 27 16 22 19 18 15 28 20 33 24 24 24 48 49 542 4 4 11 6 6 4 4 9 10 4 7 8 5 12 3 6 8 2 8 1 10 6 7 8 9 4 5 7 8 7 4 4 6 10 9 4 6 7 6 9 7 9 10 13 12 5 9 7 7 11 5 6 12 6 5 10 5 7 10 10 9 12 6 11 7 6 12 9 8 11 15 6 10 11 10 18 12 10 8 7 16 11 16 12 19 18 17 18 13 10 11 20 11 17 18 27 19 21 13 17 22 9 24 16 18 24 20 15 22 13 19 22 28 25 23 16 13 18 21 16 21 33 25 24 25 29 26 21 19 14 19 12 15 17 11 10 18 16 14 9 22 7 5 9 7 4 3 10 12 5 2 5 6 8 2 2 5 4 5 5 5 6 4 7 4 8 5 4 7 3 5 4 4 3 2 5 6 4 3 2 4 3 10 7 8 8 6 8 5 9 11 13 12 9 13 7 6 10 9 5 18 14 7 3 12 10 4 9 13 6 4 9 5 10 11 7 10 13 13 7 10 10 8 4 10 8 10 10 5 9 4 6 7 8 3 5 4 7 3 9 8 4 7 0 3 6 5 5 6 2 4 1 3 5 2 6 5 4 5 2 2 6 1 4 6 4 4 5 7 4 4 3 2 5 2 6 2 4 3 0 5 2 5 4 2 5 1 1 1 3 4 2 2 1 2 3 6 0 4 3 1 3 3 3 1 1 3 2 4 2 3 2 4 1 2 2 3 3 1 3 2 1 1 1 4 0 2 0 0 4 2 0 3 0 6 1 0 4 3 4 1 5 4 0 5 1 0 3 3 3 2 1 4 0 3 0 3 4 3 3 1 6 5 4 4 1 3 2 1 5 2 1 1 2 4 3 6 5 5 3 0 1 2 4 5 1 6 1 5 4 1 3 0 3 2 6 3 3 7 1 3 11 7 1 4 0 2 5 2 1 1 1 4 3 7 6 2 5 1 3 2 3 3 3 2 5 4 3 4 2 3 5 2 1 1 2 6 6 2 3 1 3 3 2 4 3 0 3 2 2 6 5 7 2 4 3 1 3 0 0 0 0 3 3 2 2 2 1 2 1 1 0 2 3 0 1 1 4 1 3 1 0 0 3 1 2 3 1 0 0 2 1 0 0 1 1 0 1 4 1 0 0 0 3 0 2 0 0 0 1 0 2 0 1 1 1 2 0 1 2 1 0 3 0 0 2 3 1 2 1 0 0 1 1 1 0 2 1 0 3 0 1 0 4 1 0 0 0 1 0 0 0 0 0 1 0 1 0 2 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 0 3 1 0 0 0 0 0 3 0 0 0 0 0 0 0 1 1 2 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 2 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 2 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 0 0 0 3 2 0 1 0 1 1 0 1 0 0 1 0 1 0 2 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 2 1 1 0 0 0 0 0 0 0 1 2 2 1 1 2 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 2 0 0 0 1 1 1 0 0 0 0 0 0 0 0 2 0 
];
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
 1446267 856295 589972
 1340348 794263 546085
 1313967 778234 535733
 1312042 777792 534250
 1292781 769844 522937
 1374960 825710 549250
 1292998 774394 518604
 1374492 810223 564269
 1265326 760485 504841
 1273312 765745 507567
 1375959 822494 553465
 1242660 754109 488551
 1287886 773432 514454
 1203732 732914 470818
 1183500 722674 460826
 1301653 788774 512879
 1181219 724712 456507
 1228066 751658 476408
 1164393 720239 444154
 1181849 726354 455495
 1164266 723615 440651
 1164852 724605 440247
 1118358 699914 418444
 1132002 706389 425613
 1079915 682026 397889
 1132632 714412 418220
 1085444 683943 401501
 1051872 667994 383878
 1072219 683541 388678
 1035205 664571 370634
 128627153 111307264 17319889
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
8 4 0 1
2 0 0 0
1 3 0 0
1 4 0 1
6 2 0 0
1 4 1 0
9 4 0 3
120 2 1 2
118049 6 0 1
1021850 9 0 0
2643085 5 1 1
6136115 7 3 6
11411444 14 38 18
18316152 18 179 83
22450467 39 219 126
23197998 99 284 239
18651035 238 553 547
12995230 422 918 902
7880444 633 1434 1388
3737198 934 1862 1857
1256535 1185 2277 2312
259186 1678 2701 2653
25251 2259 3170 3103
4561 2943 3650 3743
4773 3614 4381 4363
5240 4434 4856 4884
6137 5320 5617 5661
6936 6013 6409 6345
7493 6787 7037 7034
8036 7493 7497 7581
8232 8094 8015 8180
8844 8555 8377 8548
8842 8638 8672 8698
8870 9008 8890 8923
9193 9032 9008 9048
9198 9241 9220 9193
9334 9702 9174 9189
9330 9480 9534 9412
9507 9556 9337 9457
9728 9920 9661 9667
9841 9849 9494 9824
10137 10202 10108 10144
10383 10459 10289 10549
10782 10926 11104 10873
11285 11450 11283 11323
11829 11748 11940 12124
12693 12432 12470 12502
13120 13142 13264 13226
13797 13595 13589 13651
14376 14227 14138 14153
14606 14461 14442 14494
14643 14607 14548 14861
14786 15029 14900 14980
14813 14771 14838 14915
14465 14610 14439 14607
14272 14426 14304 14355
13687 14065 13960 14087
13460 13485 13343 13530
13040 13092 13003 12898
12762 13005 12738 12639
12619 12492 12659 12403
12878 12808 12532 12762
13090 13088 12829 12806
13420 13590 13784 13626
14600 14553 14618 14696
15634 15830 16125 15991
17965 17808 17753 17865
20186 19991 19985 19941
21679 21549 21759 21591
24465 24648 24164 24504
26135 26269 26157 26269
29378 28950 29678 29274
31967 32121 32120 31889
33602 33611 34124 33906
34286 34432 34088 34336
35927 35665 35584 35510
33753 33913 33625 34085
28250 28009 28316 28079
27671 27760 27669 27471
26449 26282 26391 27007
15534 15369 15462 15571
9205 9146 9274 9160
603 577 558 594
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
