A = [
758422 789912 3241954 638250 663033 597941 580347 586747 568788 532984 528739 530553 522841 515099 507981 500525 493971 490395 484366 481297 477760 472828 470483 468914 471686 564245 564378 565668 659649 661518 665003 667437 671916 675631 675697 673091 665979 660197 657618 648788 645603 643229 640056 638475 636778 628243 625010 618793 612171 607869 603065 598871 596236 592316 587947 584338 580130 574321 570610 565786 560124 556316 554648 553071 545800 543010 540811 535678 531335 525331 520315 516583 512316 508573 506131 503027 499192 494329 488656 485077 480833 475287 471075 469236 465328 460688 456892 453017 450347 445447 440213 437365 433107 429310 425186 420257 419781 415327 412005 407228 403205 400415 394487 392211 388661 384437 382465 380427 374898 373344 369581 363777 362184 357779 355480 352876 348208 344334 342028 338686 335788 332541 328238 326109 322500 319535 316495 312740 310890 307938 305332 301356 298179 295716 293073 289229 285961 284445 281393 278408 275393 272619 270435 267280 264535 262138 259277 256681 254651 251752 251278 247859 245362 241063 238663 237524 234685 232937 230123 226736 225643 222083 220073 217593 214982 212306 210471 208904 205636 203646 201534 199647 196619 195347 192422 189919 188806 185936 183603 181721 180267 177910 175902 173868 171676 169657 167440 165758 164607 161618 160516 158621 156160 154998 153174 150725 149516 147890 145794 144295 142484 140493 138929 137322 136201 133992 133101 130292 129369 127594 125899 124800 123109 120678 119486 117596 116902 114966 113963 112251 110812 109579 108698 106209 105956 103714 102604 101821 99984 98265 97180 96489 94873 93491 92105 91664 90043 88868 87341 86631 85416 83987 83122 82023 81090 79854 79423 77872 77010 76267 74889 74192 73012 71715 71353 69611 68897 68158 67373 66356 65929 63909 63408 62621 62053 60972 60148 59618 58585 57876 57268 56443 55473 54643 54198 53142 52322 52022 51175 50585 49961 49402 49044 48005 47088 46481 45694 45672 44333 43838 43365 43090 42076 42457 41192 41208 40395 39560 38788 38873 37671 37367 36687 36226 35722 35345 34906 33893 34169 33128 33219 32518 32508 31556 31505 31162 30243 30161 29380 29041 28752 28241 27564 27164 26986 26733 26070 25405 25031 24891 24523 24166 23915 23846 23173 23028 22467 22312 22170 21396 21220 20969 20768 20649 20180 19990 19922 19758 19305 18815 18778 20199 18646 18132 17976 17756 19759 17029 17378 16940 16565 16495 16069 15950 15558 15387 15220 15107 14733 14543 14459 13989 13820 13477 13388 13239 12862 12976 12635 12320 12226 11980 11916 11802 12107 12021 11604 11816 11728 11491 11614 11220 11148 10979 10768 10716 9991 9681 9585 9674 9404 9425 9307 9317 9005 8794 8638 8645 8549 8528 8266 8119 7923 8133 7853 7803 7635 7535 7429 7278 7136 7197 7079 7078 6985 6827 6717 6744 6648 6644 6359 6333 6410 6169 6145 5960 6085 6034 5883 5759 5846 5561 5635 5466 5523 5335 5384 5156 5151 5058 5077 5112 4875 4936 4936 4730 4759 4745 4628 4457 4365 4405 4198 4179 4274 4129 4101 4072 4075 4089 3913 3904 3844 3875 3906 3710 3760 3718 3496 3325 3483 3615 3417 3452 3346 3404 3399 3284 3313 3249 3219 3179 3172 3142 3059 3095 2959 3016 3010 2917 2867 2891 2856 2835 2806 2793 2827 2728 2854 2612 2648 2639 2566 2626 2601 2593 2556 2499 2471 2476 2371 2383 2496 2371 2366 2283 2215 2257 2231 2308 2258 2251 2194 2181 2171 2219 2113 2121 2013 2047 2057 1919 2014 1917 1995 2007 1926 1828 1958 1843 1822 1864 1827 1818 1894 1805 1719 1750 1802 1703 1731 1725 1737 1763 1710 1636 1637 1619 1637 1618 1662 1659 1604 1589 1723 1586 1583 1443 1539 1462 1524 1469 1489 1447 1428 1447 1421 1423 1338 1379 1316 1340 1327 1383 1327 1338 1406 1315 1279 1287 1286 1245 1293 1297 1334 1177 1261 1223 1194 1199 1275 1232 1236 1207 1136 1107 1178 1129 1146 1204 1074 1149 1120 1072 1087 1065 1072 1093 1060 1049 1031 1006 1014 1058 971 992 982 970 960 985 947 934 923 996 940 908 905 880 873 922 901 887 842 890 853 878 816 850 816 881 850 822 854 793 814 787 865 758 783 787 825 785 780 770 723 744 774 761 778 773 745 736 754 713 732 716 690 684 692 720 711 730 688 710 657 679 699 672 685 717 710 687 676 673 693 717 714 671 690 682 662 631 635 651 628 581 621 585 661 650 629 659 635 650 610 654 632 619 648 633 660 660 626 633 622 608 619 641 688 700 642 604 728 803 642 660 634 616 609 616 526 582 578 524 501 539 524 508 503 514 499 503 488 551 517 473 512 500 489 486 515 502 466 515 480 533 455 548 503 489 464 532 481 452 484 486 462 518 414 476 456 500 418 511 454 474 480 479 454 439 441 393 380 379 383 378 402 383 356 370 376 395 398 389 411 384 359 410 369 413 396 370 404 380 369 372 422 363 352 357 353 368 398 343 394 381 346 348 337 338 364 405 365 365 366 343 335 313 336 343 331 310 299 297 293 319 306 278 283 296 307 295 265 277 294 275 271 264 285 277 247 299 275 324 311 291 305 294 304 316 283 314 304 314 293 295 265 305 289 296 287 250 249 276 264 253 285 243 233 271 208 235 259 221 251 266 295 284 230 254 264 228 245 239 241 253 257 256 256 250 261 255 251 244 270 266 239 269 245 231 240 231 207 222 195 167 199 195 225 202 206 218 212 182 174 198 221 262 185 189 192 192 213 196 216 190 191 234 199 201 189 162 169 179 185 149 188 148 147 161 140 167 148 158 184 144 141 142 147 133 166 167 143 159 152 137 163 147 139 155 167 135 141 197 153 143 150 137 157 159 149 147 139 129 150 128 147 132 135 149 136 119 132 133 135 131 156 140 148 178 114 131 156 139 157 138 139 131 141 132 158 149 151 152 145 138 134 141 129 118 152 114 117 108 116 151 148 141 123 125 134 141 113 114 134 148 158 126 116 140 120 125 161 128 104 147 123 116 126 122 133 125 136 114 113 111 104 135 100 91 101 120 128 104 106 132 96 128 131 117 118 112 123 103 101 113 122 98 96 119 103 126 108 99 90 100 111 96 100 85 103 89 110 107 130 116 93 97 107 128 102 101 94 113 88 103 107 109 117 96 94 87 99 105 80 90 95 102 96 89 100 85 93 94 83 92 109 88 103 103 108 99 100 107 84 96 82 91 91 102 85 82 94 83 113 90 104 96 83 107 95 103 89 95 95 95 107 88 109 81 102 97 113 82 99 87 120 135 122 113 81 108 98 99 82 94 89 77 93 82 67 85 101 58 76 63 65 66 76 64 89 72 60 64 64 90 96 78 86 65 69 64 61 51 60 60 68 61 70 59 62 74 60 56 55 46 63 48 66 64 53 52 67 50 68 50 67 55 58 59 50 63 60 63 67 69 57 55 67 67 65 65 59 57 50 60 46 63 40 55 51 68 67 61 50 40 57 50 48 58 53 55 49 57 70 57 58 69 57 51 56 67 89 74 62 83 63 75 65 69 61 68 58 45 50 45 54 66 56 53 49 50 47 43 48 45 50 38 51 45 40 50 39 37 42 44 36 39 37 43 44 33 49 47 45 41 35 53 35 45 45 46 45 30 38 33 48 41 49 41 37 32 45 37 39 47 40 38 37 39 42 34 43 32 33 39 37 30 38 44 30 40 30 28 23 28 24 26 37 19 36 25 32 31 27 29 29 26 43 37 31 28 40 39 34 32 44 35 52 31 27 40 38 33 47 46 52 41 46 44 43 34 38 38 38 59 42 55 46 53 51 50 41 49 51 53 56 36 48 56 48 43 37 50 56 49 41 44 48 42 39 41 50 31 33 26 28 28 31 23 26 37 25 36 31 34 45 27 24 32 29 22 30 32 27 29 28 19 24 19 30 29 22 26 17 21 23 18 23 23 19 31 23 25 18 26 28 24 26 19 13 28 27 23 30 23 24 24 20 19 21 22 28 25 23 24 21 15 25 18 18 17 24 17 18 16 17 22 15 21 21 28 24 22 23 27 24 17 15 24 20 23 19 17 15 25 14 27 25 17 22 21 25 16 26 15 25 22 15 19 18 20 21 16 14 18 16 12 26 19 14 21 25 20 27 17 20 17 25 17 18 16 10 7 17 19 18 16 16 18 18 10 19 18 16 20 16 18 17 28 24 22 22 17 21 17 18 18 15 29 20 31 22 28 23 25 27 20 26 33 24 22 19 21 17 23 24 22 24 17 12 18 13 19 17 17 13 21 24 12 17 27 22 12 20 19 16 22 22 12 13 19 15 25 13 15 18 21 22 16 17 17 17 15 20 13 14 19 18 17 22 25 13 9 11 17 17 17 20 13 23 12 20 21 30 17 15 23 24 14 19 23 19 13 18 19 15 18 17 9 13 17 13 16 21 11 17 16 12 14 13 13 25 13 13 13 12 9 14 9 10 16 16 13 15 19 10 15 10 30 22 15 15 17 16 20 13 13 14 10 7 11 12 14 12 14 11 12 15 16 18 10 10 21 13 17 13 12 10 15 12 12 14 8 15 14 7 13 11 7 11 19 11 15 13 10 11 8 10 9 14 12 8 18 7 10 12 12 8 14 12 16 14 10 15 7 14 9 10 12 3 13 9 12 24 14 11 3 15 5 13 18 8 13 9 3 12 13 15 9 13 4 9 9 6 14 9 12 15 22 14 10 8 10 12 15 20 10 12 13 13 7 8 14 11 14 12 9 14 11 11 10 8 16 14 14 8 12 8 20 12 16 10 16 18 5 15 8 6 19 12 15 17 18 13 12 11 18 12 15 17 7 7 12 14 9 11 12 15 17 16 14 20 17 10 16 14 8 7 8 12 14 10 15 16 9 14 12 11 9 8 14 16 12 9 9 10 13 17 11 9 16 9 8 14 12 10 12 11 19 10 16 14 9 17 12 12 7 13 16 5 5 12 10 7 13 7 11 13 6 17 12 2 14 10 13 15 10 8 5 14 8 7 9 6 8 10 17 17 8 10 14 15 9 13 14 6 8 15 15 11 24 13 16 13 13 10 11 10 11 16 10 14 9 12 8 11 12 12 7 9 13 12 11 10 19 11 10 11 11 
];
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
 1282241 528068 754173
 93726 37750 55976
 167022 69058 97964
 929907 418105 511802
 616513 275480 341033
 1028117 466354 561763
 1902672 863390 1039282
 1531032 653515 877517
 951362 424269 527093
 2224175 1029541 1194634
 859558 357887 501671
 59379 24962 34417
 2030585 930546 1100039
 31849 13436 18413
 56623 23711 32912
 2784809 1316929 1467880
 58980 25437 33543
 691800 289881 401919
 3871927 1961187 1910740
 689429 296427 393002
 20 9 11
 26835856 14111831 12724025
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
58 112 0 0
61 17 0 0
168 26 0 1
246 17 1 0
177 28 0 0
113 33 33 1
316 71 106 16
1709 75 144 34
9697 97 194 69
37725 133 310 110
85729 139 358 162
180783 203 489 288
356593 246 717 445
726944 378 969 658
1340871 586 1263 1064
2238761 900 1869 1610
2807642 1509 2602 2376
2543091 2448 3345 3379
1758750 4044 4466 4468
934412 5540 5504 5380
367031 6978 6232 6073
88625 8344 6366 6471
18827 8316 6775 6601
12667 7477 6937 6855
10981 7801 7123 7174
10264 8554 7218 7250
9885 7913 7610 7625
9787 7973 8042 8172
10049 8531 8644 8686
10391 9052 9251 8940
10782 9463 9781 9829
11698 10502 10584 10640
13192 11900 11594 11532
14445 12797 12640 12776
15435 14097 14227 14255
16677 15779 15737 15544
18722 17384 17557 17903
20712 19765 19945 19950
22884 22441 22344 22491
25447 25168 25346 25563
28749 28616 28803 28782
32554 32194 32595 32523
36735 36709 36458 36508
41767 41928 41908 41579
47479 47599 47296 47590
53572 53760 54019 54663
60397 60468 60964 60557
68148 67732 67664 67427
75344 75173 75198 75420
83247 82763 83215 82623
90152 90203 90262 89958
96051 95948 95851 96275
101074 101568 101755 100467
106139 106371 105851 106870
111475 110952 112325 111828
115174 115890 115121 115404
122107 122495 121981 122159
128200 127753 127253 127524
133445 132938 133263 132873
137980 137999 137823 138774
143740 143904 143521 143806
144710 143980 144640 144856
138654 137683 138469 137947
119173 120008 119782 120079
88872 89200 89224 87863
49144 49616 49483 48492
19059 19637 19374 19155
8879 9141 9216 8552
7038 6465 6324 6520
5571 5983 7453 5383
3934 4271 4047 4182
3549 2508 2674 3203
229 229 120 76
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
