A = [
399454 366873 697666 406682 382888 382439 360836 379724 377330 368392 382941 393555 407351 418599 421749 427359 429698 434133 433639 427651 430039 430552 428651 431742 438516 714923 712607 722299 999502 1005829 1040477 1061312 1065524 1096269 1105284 1094507 1082015 1069059 1062019 1048819 1045901 1049200 1046859 1051350 1054945 1040522 1027629 1017327 996916 983962 976354 969887 975354 971761 968627 964175 956344 943663 925474 913031 903495 892060 890465 888725 887118 882991 876612 865550 854041 841062 830866 822889 815996 813755 808891 805189 796833 785847 773535 761667 746345 735358 728804 719835 715521 711176 702886 691484 681721 671917 659947 647826 639513 630029 625374 620434 615446 610327 600437 591494 581106 572174 563835 556468 548761 545345 539381 533260 527762 520722 510416 503298 494937 486075 480889 476509 471905 465320 460720 454378 447972 438900 431415 424701 417806 413916 407514 403714 398808 392976 387981 381092 374865 368820 362429 357179 352501 349238 345195 340398 335658 329584 324450 317828 312619 308356 303731 299161 293546 292405 287422 282788 278090 272683 268338 263302 258890 255964 252564 249249 246231 241699 236983 233100 227593 225310 221723 217912 215731 211328 208409 205709 201582 199181 195208 191628 187477 185356 182659 179275 176244 174270 171865 168608 165559 162863 159207 157704 154090 153009 149145 147341 144677 142437 140547 137402 135292 132960 129990 128246 126496 124202 122273 120340 118540 116073 113571 111138 109088 107940 106623 103929 102494 100983 98314 97109 95602 93573 91913 90613 88829 86826 85876 84072 83001 81142 79477 77991 76360 74821 73670 72712 70660 69330 68505 67593 66028 64938 63897 62667 60897 60157 59030 58131 56335 55595 54616 53870 52628 51887 50700 49812 49034 47922 47186 45744 44921 44599 43374 42529 41608 40765 40090 39190 38465 37848 37119 35966 35597 34913 34357 33605 32673 32386 31570 30932 30456 29366 28969 28605 28155 27617 27227 26416 25881 25254 24944 24084 23718 23178 22798 21989 21674 21378 20837 20403 20360 19813 19181 19137 18445 18151 17830 17359 17068 16497 16316 15751 15564 15576 14984 14613 14209 14193 13628 13473 13218 12832 12764 12464 12257 11946 11512 11571 10950 10917 10661 10301 10188 10196 9932 9728 9377 9238 9045 8979 8580 8592 8281 8162 7976 7736 7638 7645 7276 7228 7088 6895 6623 6793 6565 6284 6189 6122 5877 5813 5575 5520 5414 5261 5135 5092 5068 4891 4834 4743 4572 4440 4365 4314 4213 4098 4018 3911 3872 3768 3733 3651 3559 3438 3326 3395 3235 3101 3060 3151 2959 2851 2883 2753 2809 2642 2637 2664 2512 2479 2470 2440 2292 2331 2220 2211 2263 2141 2079 2045 1985 1973 2004 1919 1847 1795 1701 1762 1725 1759 1674 1557 1652 1511 1562 1490 1461 1439 1405 1441 1397 1397 1320 1333 1260 1236 1249 1184 1202 1180 1111 1181 1070 1031 1058 982 1062 997 1008 988 913 911 925 938 868 870 904 874 856 847 787 762 768 815 729 775 769 745 679 694 701 708 719 640 686 644 660 589 627 563 611 587 636 550 558 594 535 550 537 560 514 521 520 550 483 521 487 473 477 505 441 446 464 461 478 471 461 483 426 422 415 412 406 443 420 419 379 396 387 410 390 349 337 376 371 376 342 359 353 363 321 343 347 334 346 335 362 331 276 313 302 309 324 281 300 316 322 287 284 306 289 288 302 312 257 251 276 294 259 311 281 299 237 242 267 275 256 259 293 266 277 239 269 257 261 255 232 257 231 250 258 232 253 242 254 254 206 232 244 216 228 231 231 255 200 208 215 224 233 225 225 215 244 216 232 196 216 200 193 239 223 223 207 187 223 214 194 197 204 190 187 198 204 191 189 166 195 198 183 192 187 193 194 170 193 177 169 198 210 191 200 183 169 187 155 153 155 169 188 171 165 144 187 167 157 185 169 180 158 198 163 163 182 169 137 125 150 169 132 168 152 148 166 128 138 146 158 144 123 156 143 158 140 145 165 150 146 151 128 145 164 129 145 164 129 145 150 133 140 152 173 126 146 127 113 130 115 123 135 139 112 128 114 117 125 136 138 135 135 135 150 139 135 136 153 143 133 118 119 124 104 118 131 102 131 153 140 102 119 113 122 106 122 135 127 119 113 106 124 103 93 112 109 101 125 103 112 108 101 104 83 93 92 89 96 117 96 106 113 107 90 110 107 100 100 87 111 86 96 92 83 98 85 80 77 93 86 84 91 100 95 102 91 98 113 83 87 95 97 80 82 77 65 92 93 56 84 92 84 85 73 82 67 85 86 79 81 87 88 90 83 91 77 86 81 84 95 73 75 86 86 60 71 87 63 83 85 64 79 77 71 65 76 61 71 72 55 79 61 63 78 70 66 63 57 68 70 57 72 61 81 73 68 80 66 69 58 63 62 66 51 59 62 60 61 59 52 75 61 57 58 54 72 60 66 39 56 68 56 63 69 54 50 43 37 49 69 62 54 39 43 59 50 46 50 44 56 55 54 46 52 59 60 42 46 66 49 49 48 61 55 57 49 53 48 40 49 45 46 57 39 31 43 40 52 46 42 38 41 37 53 54 51 46 47 46 58 57 31 36 55 41 50 38 41 45 39 42 50 42 41 46 41 48 32 40 52 38 38 38 43 41 38 35 32 40 37 41 42 40 50 42 33 34 38 38 38 36 33 31 28 30 33 39 30 41 38 41 33 28 38 39 34 23 48 35 27 22 34 37 31 39 40 36 36 31 26 28 25 28 35 37 33 35 31 37 36 22 31 22 29 36 25 32 29 40 25 39 24 29 31 39 23 24 29 28 27 20 30 27 33 40 31 28 29 36 20 28 29 29 34 27 30 20 22 26 19 25 24 34 22 25 31 22 21 26 32 24 30 20 30 17 26 32 16 23 24 23 16 26 21 29 27 23 32 26 21 19 27 19 22 21 13 22 25 12 19 15 18 22 17 13 19 16 23 16 28 16 29 22 14 24 16 24 26 18 18 24 22 18 15 15 17 21 17 20 25 16 13 23 13 14 14 13 20 14 17 14 17 14 18 18 20 18 10 19 29 19 17 19 13 11 26 12 19 16 19 13 18 15 11 26 22 21 12 20 39 36 25 16 17 14 16 16 13 13 8 14 20 15 19 12 13 17 11 12 14 14 16 8 9 21 15 12 14 13 20 17 17 16 13 12 16 18 11 16 14 11 14 11 15 15 23 14 15 9 18 14 7 8 8 18 13 17 14 12 12 12 10 5 10 8 9 11 12 13 6 10 12 13 12 6 17 7 13 3 11 11 10 11 14 5 16 13 8 9 12 4 13 12 11 12 12 15 10 11 14 11 10 14 16 9 10 7 12 10 11 7 10 9 9 14 12 12 6 7 7 13 8 7 9 5 9 9 8 8 13 8 10 13 7 13 10 10 10 6 5 11 13 12 11 8 7 13 11 7 4 14 8 12 6 9 13 7 12 6 21 9 4 7 5 7 14 6 7 4 10 8 7 9 11 10 8 11 3 6 5 12 9 12 8 8 6 10 9 9 8 4 4 5 8 9 7 4 4 7 8 6 6 8 3 4 5 10 8 5 6 9 7 9 8 6 5 9 6 6 10 8 5 10 5 7 6 6 4 7 8 9 7 10 9 7 9 9 5 6 6 4 3 5 10 7 7 7 6 10 8 6 13 4 5 8 7 6 3 10 5 4 8 7 5 6 7 7 5 6 7 6 1 6 4 2 7 8 7 4 7 5 3 7 2 7 5 6 4 4 2 10 6 3 4 3 7 8 3 9 4 6 6 3 6 3 3 1 7 5 3 5 6 7 4 5 8 7 5 4 6 8 7 6 3 5 3 1 6 6 7 2 2 7 5 4 5 6 6 8 4 3 3 2 3 6 7 5 3 3 5 10 2 8 6 8 3 6 6 5 4 0 5 4 9 3 8 10 1 3 3 6 6 2 9 2 4 2 2 1 5 5 1 2 2 4 4 3 7 4 3 6 2 2 6 3 1 1 0 5 3 5 3 4 3 2 2 5 2 0 2 4 2 4 1 5 5 5 2 1 1 2 4 5 3 2 1 2 4 2 2 2 1 1 3 3 1 4 1 2 3 0 2 1 1 1 0 4 5 0 1 2 0 5 4 6 3 2 5 3 3 2 2 1 2 0 4 2 3 2 2 1 2 3 5 4 3 2 1 1 4 0 2 1 4 3 4 2 2 0 0 2 1 2 5 4 2 3 1 1 2 4 0 2 1 1 0 4 2 3 1 4 2 2 3 3 0 3 3 1 1 2 2 3 2 3 1 1 2 4 2 4 1 0 3 0 4 3 4 2 1 2 2 1 3 3 2 3 1 1 0 3 0 4 4 0 0 1 2 1 4 2 0 2 4 2 0 3 3 3 1 4 1 1 0 4 1 3 0 1 0 4 1 0 2 1 2 2 2 1 1 0 1 1 0 1 3 3 0 3 1 1 3 0 0 0 3 3 1 0 1 1 0 3 2 1 1 0 1 2 3 2 1 1 5 0 0 0 3 2 0 1 2 3 2 3 6 1 1 0 0 2 1 1 0 1 2 0 0 2 3 1 3 0 2 1 3 0 0 0 1 0 0 3 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 3 1 0 0 1 1 1 3 3 1 1 2 2 1 1 1 2 1 3 2 0 2 2 1 2 0 1 0 2 0 3 0 1 0 1 1 2 0 1 2 0 1 1 1 0 0 1 2 0 0 1 0 1 1 3 0 1 1 1 1 0 1 1 1 0 1 2 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 0 4 0 0 0 2 1 0 0 2 1 1 1 1 1 2 0 1 1 0 1 2 0 2 0 2 0 1 1 1 1 1 2 1 0 0 2 0 0 0 1 2 0 0 0 0 0 0 1 0 0 0 1 0 0 3 1 1 2 2 0 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
 145528 119416 26112
 238681 195620 43061
 86829 70704 16125
 574332 471204 103128
 67200 55131 12069
 155816 127961 27855
 105833 86871 18962
 201213 164628 36585
 37595 30807 6788
 714111 586866 127245
 434 365 69
 26430 21779 4651
 20856 17119 3737
 176431 145894 30537
 21813 18143 3670
 20746 17156 3590
 57554 47798 9756
 93671 77554 16117
 1218718 1004629 214089
 186487 155325 31162
 24807 20653 4154
 64447 53963 10484
 58650 49426 9224
 124009 103738 20271
 1533476 1271525 261951
 35829 29865 5964
 200562 169510 31052
 93155 79507 13648
 245082 208746 36336
 409516 345728 63788
 49950443 42710545 7239898
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
4 19 0 0
2 0 0 0
1 1 0 0
3 3 1 0
2 5 0 1
4 5 74 2
193 5 305 33
2674 15 364 107
17562 15 644 265
65845 23 957 570
165966 39 1329 904
388370 94 1964 1433
768058 216 3044 2397
1401078 638 4614 4127
2070361 1364 6817 6599
2551414 2744 10360 10303
2350634 3789 15062 14667
1595716 4954 20822 20790
781149 7654 28813 28614
255717 11786 37125 37364
83269 17571 45936 46355
62325 24701 54462 53712
65556 37246 62603 62676
71268 51725 71627 72263
78007 69437 82030 82668
87990 88898 94018 93637
98571 109242 106136 106766
110716 128995 120727 120130
123462 146192 134337 134699
134904 162418 147886 148070
145998 174771 159266 159285
154233 184613 167266 167913
160776 191942 174804 175439
165122 195420 178183 179442
169252 196610 181191 181693
169575 195333 181113 180965
168225 191609 178395 179188
168943 187628 177496 177190
169512 183444 174838 175657
168161 180802 173968 174356
169108 178770 174857 173567
170674 178428 174147 175676
173217 179360 176347 176753
176946 182592 179381 180298
183328 187230 186589 185762
191111 194666 192923 193392
201841 204951 203345 203288
212868 215468 214199 215098
225583 227211 226063 226925
239126 241061 239288 238664
252037 252306 250873 252359
261141 263696 261290 262598
268457 269876 269426 268991
271433 274588 272726 273530
271510 273125 272239 272702
265366 266994 265359 265395
253982 255916 253670 255061
238465 239823 239982 239131
218989 221892 220415 220464
198972 200065 199625 199432
180081 180864 180460 180589
160137 161275 160337 161697
141678 142940 141979 142643
125638 125959 124864 125779
114505 114843 115020 115469
109006 109426 109490 109097
107142 107481 107457 107485
101076 101940 101703 101523
98790 98656 98526 98504
99872 99101 98965 98938
96414 96255 96523 96462
91520 91985 91958 91805
83476 83885 83585 83910
74201 73255 73104 73582
63241 63651 63278 63760
51384 51576 51270 50960
37071 37068 37122 37332
26242 26515 26550 26463
20540 20270 20189 20505
13271 13516 13441 13496
7211 7262 7308 7261
2959 2890 2821 2885
148 137 154 131
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
