A = [
241812 201109 210172 205787 207069 198251 186798 181780 184284 177476 178819 177488 174500 172261 170616 170799 167451 165116 164666 162869 160348 160317 157474 154197 155167 154410 149407 147253 143851 140906 140661 140175 138133 141689 139422 137023 137554 135037 132901 133149 131475 129041 129364 127220 125492 125509 123811 121322 121779 119014 117711 117804 117426 115485 115581 113207 111370 110950 109284 108170 107235 106795 106598 105656 103601 102452 103236 101175 100117 100315 98691 97251 98017 97068 94187 94840 93935 92640 91826 90057 89722 90349 88312 86944 86512 86835 84585 85277 83358 82399 82068 80462 79785 80539 79049 77063 76858 76248 75312 75949 74902 72677 73526 72429 70626 71259 70478 68984 69309 68504 67694 66950 67258 65067 65365 64760 63223 63258 62304 61491 62881 61115 59563 59598 59752 58603 58533 58181 57166 57012 56532 56089 55308 55319 54344 53987 53336 52293 52174 51675 50557 50308 50298 49712 49461 48415 47748 48405 47644 46213 46565 46527 44885 45293 44905 44258 44645 43540 43129 43226 43057 42147 41425 40947 40694 40668 40329 39271 39261 38880 38453 38717 38097 37177 37410 36543 35772 35798 35241 35058 35181 34369 33903 33825 33265 33245 32914 32666 31453 31834 32130 31323 30847 30341 29904 30255 29890 29106 29090 28631 28770 28950 27619 27709 27828 27449 26899 26753 26635 26038 26115 25574 25226 24962 25199 24557 24425 23770 23742 23326 23062 23002 22672 22925 22063 21793 21843 21026 21180 20906 20425 20428 20433 19982 19663 19894 19925 19121 19062 18676 18401 18499 18112 17811 17303 17077 17410 16853 16246 16096 15565 15882 15587 15061 14812 14940 14675 14448 14336 13777 13783 13185 12992 13166 12609 12576 12051 12089 12004 11650 11318 11199 11127 10917 10939 10479 10470 10079 9813 10029 9641 9524 9446 9010 9191 8898 8850 8711 8590 8616 8107 8017 7981 7848 7610 7485 7199 7219 7096 6794 6914 6995 6573 6587 6531 6333 6313 6254 5833 5913 5634 5777 5610 5434 5597 5228 5033 5256 5141 4993 5013 4899 4755 4584 4621 4475 4385 4386 4339 4202 4149 4168 4092 3988 4030 3996 3951 3982 3720 3646 3583 3514 3616 3461 3272 3293 3288 3175 3226 3151 3056 3085 3048 2966 3011 2939 2968 2897 2822 2787 2728 2630 2574 2699 2700 2635 2658 2585 2429 2507 2513 2469 2317 2211 2280 2353 2086 2238 2215 2070 2041 2033 2029 1960 1946 1951 1909 1943 1897 1858 1835 1754 1805 1790 1676 1794 1843 1734 1647 1598 1658 1571 1671 1563 1643 1667 1611 1471 1505 1568 1448 1516 1420 1389 1498 1373 1439 1386 1338 1342 1315 1343 1264 1313 1427 1385 1353 1345 1321 1315 1324 1205 1148 1236 1272 1216 1204 1088 1203 1202 1198 1171 1157 1141 1174 1246 1104 1090 1077 1023 1036 1098 1029 1047 1066 1080 1094 1030 1048 1034 1078 1005 1014 1060 1101 1014 985 887 948 943 939 1012 1067 938 950 917 905 879 921 857 773 835 784 826 760 832 833 773 849 811 890 801 761 753 727 752 742 754 758 707 764 782 752 703 746 763 766 728 744 712 699 679 651 627 639 599 664 638 610 596 604 603 658 598 588 575 578 577 599 573 589 550 562 601 557 535 521 611 492 576 526 476 506 467 467 503 538 489 563 549 451 445 497 470 507 470 429 470 436 463 413 432 467 494 450 455 446 431 381 429 429 420 464 381 411 410 400 377 379 451 408 404 424 460 444 392 361 369 365 418 349 384 394 371 358 372 393 389 311 334 334 339 316 331 325 401 309 341 346 308 322 357 328 352 310 280 273 328 296 263 269 290 278 286 313 242 308 255 284 279 262 267 283 250 244 297 253 233 307 267 246 280 252 246 264 243 219 218 259 224 234 251 225 194 220 214 234 225 238 194 209 195 205 213 232 228 171 207 199 191 205 211 207 190 179 208 245 172 193 212 196 193 173 182 188 194 182 220 166 131 138 194 177 186 168 171 177 198 181 160 147 149 121 152 155 171 155 156 144 144 194 152 149 184 156 147 149 140 154 170 133 157 125 126 146 133 106 125 129 150 144 135 126 126 127 129 136 126 146 113 133 124 109 106 122 138 138 148 130 123 109 126 115 120 121 94 115 109 111 122 104 111 108 95 102 98 102 86 124 111 104 103 84 85 97 91 88 84 120 130 110 89 98 103 89 105 101 86 81 69 69 90 84 90 83 81 54 99 84 81 74 84 74 67 86 63 81 74 80 87 76 69 74 90 80 70 93 64 69 58 72 72 64 67 71 75 57 63 67 64 44 63 72 73 53 60 61 49 57 54 46 80 57 59 64 72 54 62 82 45 49 72 62 57 58 66 46 59 42 42 52 37 36 48 34 32 57 52 45 44 47 48 47 49 43 48 49 46 51 39 47 39 42 37 40 46 34 70 79 52 58 59 53 47 46 45 55 54 59 62 62 70 52 47 38 49 48 59 43 47 59 54 42 46 48 45 43 44 55 42 36 73 59 34 53 50 45 42 34 66 48 71 42 45 61 61 40 63 48 46 31 42 57 52 42 47 50 47 59 42 41 41 53 49 41 39 33 37 26 37 38 40 38 36 32 24 46 43 28 33 47 41 41 39 41 45 44 48 30 55 49 41 43 42 48 30 33 32 24 36 40 36 43 39 43 32 39 30 41 43 39 32 23 49 32 38 39 50 34 26 29 42 28 42 26 19 30 34 29 33 16 26 32 20 39 21 32 32 30 56 28 25 28 41 57 39 49 34 35 30 36 40 41 34 41 27 33 28 34 35 34 40 23 24 38 25 32 51 21 20 15 27 26 17 39 21 28 17 37 27 36 30 29 21 21 19 27 27 25 26 25 22 27 37 32 24 26 39 14 19 22 21 30 42 26 20 20 24 29 18 19 30 19 21 22 28 36 17 25 17 28 27 30 29 15 26 26 21 33 39 33 18 15 12 39 23 19 18 18 19 27 25 18 32 19 24 21 15 31 25 20 22 31 16 22 21 25 17 23 8 28 18 18 21 18 19 11 12 10 16 15 13 14 19 15 14 9 18 35 20 11 12 23 12 16 53 15 8 16 22 5 20 36 14 11 13 15 12 12 16 13 21 13 14 21 9 13 12 19 10 17 19 18 11 16 15 18 13 17 13 19 19 6 11 14 17 15 12 21 14 12 14 18 14 16 19 17 21 16 21 11 17 14 13 17 13 17 15 23 8 13 19 23 43 23 21 15 25 21 21 16 11 18 17 17 15 11 16 24 22 12 19 18 11 16 18 12 24 13 17 8 16 19 10 15 14 13 7 21 15 19 16 15 7 14 15 14 8 12 13 11 12 6 19 22 15 14 24 20 15 10 19 25 9 13 22 12 11 11 20 12 13 20 17 15 10 11 15 19 14 17 11 9 15 21 19 14 10 12 37 16 11 15 17 15 16 5 16 9 13 21 17 24 9 9 10 15 15 9 10 15 9 19 11 7 11 9 7 9 11 7 15 15 13 9 8 14 20 10 10 6 24 18 9 13 10 10 17 15 16 16 11 13 31 25 7 11 14 10 16 8 3 15 12 15 8 3 29 15 8 9 12 10 6 8 9 8 9 11 9 7 7 7 9 12 11 12 13 10 8 18 11 9 9 14 12 9 16 12 15 18 10 15 12 12 13 20 9 11 12 13 8 11 8 4 3 7 7 10 7 13 23 6 12 11 8 3 17 12 9 2 9 9 8 9 5 14 25 20 3 10 6 18 9 12 3 14 12 24 2 8 4 16 10 8 7 7 10 11 5 6 4 2 5 5 4 9 7 6 7 18 8 25 22 7 7 14 11 9 21 16 6 10 16 17 17 8 16 10 10 12 7 16 5 12 5 15 12 6 12 12 10 9 7 7 10 12 12 7 13 13 9 18 6 8 15 16 18 5 5 7 12 6 11 17 9 19 15 13 17 6 4 13 9 9 10 9 4 18 15 10 14 16 10 13 6 13 21 12 6 11 11 12 6 11 15 12 12 12 9 11 4 5 16 5 6 10 13 11 7 6 4 13 3 12 22 17 7 6 14 5 12 4 17 33 13 4 5 8 9 8 9 13 2 16 19 3 3 10 12 9 4 10 8 4 5 8 6 4 10 7 13 7 10 5 7 4 6 3 7 9 4 10 9 10 5 3 4 10 10 9 5 4 15 13 10 10 9 13 8 4 8 5 10 9 9 13 9 7 9 11 6 7 4 4 3 4 5 4 0 2 2 4 2 2 3 3 7 3 0 5 4 4 9 7 15 5 1 2 3 26 9 5 1 9 3 1 3 2 6 7 3 4 5 3 4 1 3 4 1 33 16 1 3 4 10 3 8 3 56 9 5 10 6 7 7 8 4 8 8 10 8 6 14 12 2 4 5 2 7 1 4 6 2 5 7 5 9 8 0 4 2 5 8 7 5 5 11 10 3 4 3 4 3 3 12 5 8 7 7 10 3 3 6 10 20 7 6 4 1 4 1 4 0 5 2 3 2 4 2 4 6 1 1 6 7 8 23 1 4 5 8 3 5 3 5 3 24 16 2 5 1 4 1 5 3 29 5 2 0 0 4 2 5 3 2 1 3 3 5 2 2 3 2 0 5 1 7 2 2 5 2 18 13 6 7 7 1 7 6 4 9 1 2 4 3 2 2 1 7 4 6 1 3 2 5 3 4 2 3 3 4 1 4 1 3 3 5 4 6 6 1 5 2 0 4 6 1 4 6 0 2 8 16 11 17 4 1 5 3 2 3 6 8 0 3 3 2 4 3 1 4 0 0 2 2 4 2 1 2 5 0 6 1 3 5 2 2 2 1 8 8 4 3 5 5 3 3 2 5 4 1 2 1 1 7 5 2 3 1 0 1 1 1 3 3 1 3 1 2 1 1 1 4 2 2 0 3 0 1 1 0 0 2 1 1 1 2 3 2 
];
B = [
0 0 0
 1195 1195 0
 686 686 0
 3659 3659 0
 1315 1315 0
 2389 2389 0
 1493 1493 0
 2597 2597 0
 3090 3090 0
 2802 2802 0
 2746 2746 0
 9349 9349 0
 1628 1628 0
 5479 5479 0
 4864 4864 0
 549 549 0
 3346 3346 0
 1908 1908 0
 511 511 0
 77 77 0
 2603 2603 0
 338 338 0
 2188 2188 0
 1080 1080 0
 141 141 0
 2966 2966 0
 3625 3625 0
 1889 1889 0
 5737 5737 0
 4525 4525 0
 3924 3924 0
 1462 1462 0
 9835 9835 0
 13310 13310 0
 10426 10426 0
 8383 8383 0
 16721 16721 0
 706785 706785 0
 7499 7499 0
 23807 23807 0
 2405651 2405651 0
 20126 20126 0
 6634311 6634311 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1 6 0 0
0 0 0 0
0 1 0 0
1 0 0 0
0 2 1 0
1 1 4 2
251 2 7 11
882 4 12 16
2739 2 27 21
6713 11 46 42
11446 10 59 45
18583 14 95 90
28750 35 137 166
53947 72 221 236
123372 172 381 368
386099 378 489 531
2698697 639 586 630
2832097 990 613 575
1167475 1246 685 726
134392 1477 938 940
1935 1712 1246 1267
1703 2106 1591 1612
1932 2422 1875 1927
3062 2904 2162 2179
3013 3442 2572 2491
2952 3725 3149 3185
3209 3920 3306 3486
3568 4173 3768 3678
4089 4329 4135 4040
4511 4838 4700 4705
5054 5335 5210 5152
5865 5988 5801 5893
6444 6791 6696 6501
7397 7427 7291 7201
8283 8350 8081 8100
9120 9222 9343 9194
10363 10456 10283 10315
11460 11507 11641 11493
12996 13055 12916 12926
14511 14576 14432 14535
16371 16767 16390 16281
18311 18272 18479 18446
20264 20568 20486 20263
22305 22509 22366 22079
23580 24143 24042 23714
24972 24786 24990 25087
25723 25704 26130 25517
26040 26239 26202 26124
26437 26476 26616 26043
26650 26821 27050 26751
26962 26600 26415 26660
26594 26638 26719 26493
25814 25751 25833 25846
24148 24130 24232 24313
21890 21878 21883 21610
18183 18249 18321 18007
15085 14995 15015 15140
13098 13212 13191 13289
12049 12303 12031 12233
11996 12123 12019 12131
12934 13096 13105 13152
14997 15058 14974 15137
28302 27810 27752 28097
9018 9333 8979 9167
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
