A = [
110101 121214 411404 96218 105928 92668 91059 92672 91491 86076 86539 86126 86385 83493 83355 81184 79145 80069 79386 78556 77955 76978 76346 76094 77203 85952 86984 86943 97332 97927 98377 98475 99282 99971 102232 100474 100584 98862 98080 95917 95294 95529 94894 93876 94379 93127 92001 92428 91164 89591 89145 90051 89102 87859 87683 85892 85907 85940 84427 84252 83605 82859 82557 81559 81344 80855 80274 79809 79720 78230 77859 76615 76481 74496 75034 74363 73186 72594 71808 71518 71195 69467 69272 69699 67507 66923 67212 66324 64998 65040 64134 63315 62951 62433 62112 61644 60176 60431 59666 58978 57812 58885 57094 57623 57376 55972 56004 56043 53789 53239 53014 52857 51861 52065 50674 49371 49317 48932 48262 47733 47536 47999 46487 46007 45223 45387 44645 44358 42629 42552 42377 41998 40977 40866 40191 39818 39171 38944 38485 37629 37022 36711 36077 36583 35829 35074 34944 34600 33899 34050 33658 32959 32380 32341 31624 30807 30620 29923 30036 29638 29107 28931 28001 27430 27295 26607 27302 26617 25737 25638 25544 24837 24349 23900 23881 23634 23244 22929 22804 22227 22374 22266 21278 20690 21352 21121 20214 20158 19409 19525 19121 19322 18763 18310 17917 17821 17718 17282 17570 16711 16980 16331 16225 15821 15732 15618 15123 15368 14911 15000 14677 14470 13998 13981 13552 13810 13138 13289 12771 12727 12435 12229 12475 12017 12402 11733 11514 11537 11316 10804 10696 10493 10434 10484 9873 10098 9650 9531 9417 9160 9193 9034 8827 8823 8994 8821 8713 8683 8393 8361 8331 7978 8058 7862 7696 7498 7586 7516 7238 7229 7354 6904 6891 6944 6765 6615 6595 6448 6562 6366 6502 6549 6644 6125 6025 5735 5512 5554 5678 5815 5465 5721 5500 5412 5320 5177 4997 4882 4968 4951 4777 4837 4684 4915 4646 4518 4468 4376 4563 4250 4198 4290 4234 4298 4309 4138 4249 4032 4030 4125 3957 3968 3898 3678 3867 3756 3766 3709 3397 3351 3321 3210 3156 3156 2925 3121 2871 2943 3014 3044 2815 2927 2829 2894 2808 2772 2974 2938 2844 2708 2841 2768 2819 2779 2612 2590 2602 2569 2364 2298 2348 2634 2296 2339 2321 2233 2708 2189 2250 2315 2185 2179 2187 2295 2024 2151 2052 2078 1960 1891 2063 1915 1944 1921 2004 2040 2040 1838 1882 1734 1712 1709 1783 1583 1725 1680 1617 1582 1637 1696 1732 1680 1792 1696 1588 1670 1482 1523 1473 1334 1436 1456 1376 1519 1485 1540 1371 1361 1442 1400 1301 1548 1326 1417 1485 1275 1388 1332 1249 1158 1243 1098 1144 1135 1143 1169 1122 1085 1231 1318 1173 1132 1218 1114 1122 1036 1273 1154 1130 1012 919 952 899 960 938 832 903 915 875 906 940 975 972 938 834 865 901 750 805 763 745 739 791 928 1151 961 1133 895 950 867 1362 1060 963 996 737 694 698 657 684 759 720 683 677 655 647 632 660 748 710 688 708 703 646 681 768 679 707 658 670 653 731 619 593 661 571 590 591 565 600 573 579 523 539 568 574 575 568 579 494 515 483 544 542 602 583 527 547 506 502 534 618 611 509 483 536 638 547 581 516 567 498 499 561 716 597 839 672 1007 688 639 788 653 675 636 648 675 579 540 508 602 585 635 561 666 590 363 369 421 404 403 452 462 559 530 575 615 627 596 569 466 485 443 487 539 496 466 493 468 486 467 450 389 495 532 472 422 435 466 453 356 314 360 340 358 418 372 359 341 373 319 345 338 343 291 356 346 329 367 355 382 294 335 359 360 294 342 333 387 302 357 379 368 339 314 322 352 305 351 275 278 335 291 311 286 254 222 234 212 247 288 271 227 223 261 266 226 252 232 254 232 192 226 210 212 243 229 237 248 248 233 223 228 244 204 292 230 191 213 198 247 267 201 217 191 240 207 201 249 199 254 226 220 258 247 197 230 212 203 191 204 175 215 198 175 210 211 197 197 209 201 193 187 208 192 181 174 174 198 194 195 212 204 178 217 201 259 192 205 193 230 206 238 230 286 282 378 457 403 283 267 277 269 281 324 186 254 286 247 294 265 283 292 284 246 187 194 223 233 202 184 175 190 184 175 176 227 206 190 197 215 264 251 284 276 220 246 280 397 262 249 180 277 282 186 260 260 341 376 186 156 155 194 178 192 157 210 191 184 187 189 218 154 149 143 235 210 160 165 376 152 118 125 196 145 136 112 126 112 132 128 173 122 128 133 110 117 119 116 156 181 149 206 170 143 144 182 187 194 150 131 206 215 159 176 151 121 130 162 146 123 124 139 159 161 130 134 103 104 97 86 103 89 74 106 80 86 78 98 92 96 87 82 91 106 90 101 107 128 121 126 135 104 119 83 83 88 84 96 96 93 106 130 95 120 126 107 110 95 120 157 108 92 90 86 71 83 70 104 101 59 87 74 92 62 87 66 83 98 79 89 122 84 65 89 84 61 96 74 71 86 73 72 71 86 73 62 80 66 96 79 79 97 81 101 67 58 80 72 86 79 72 52 75 55 56 69 54 67 52 54 67 56 68 77 48 70 91 50 47 55 71 50 71 54 98 62 58 49 53 59 68 48 85 65 48 54 52 48 52 50 67 53 51 71 51 61 66 46 54 63 53 47 67 72 55 63 64 63 70 69 45 42 55 47 48 52 40 54 63 40 59 40 63 44 46 40 49 45 48 54 49 54 47 55 61 44 61 59 60 56 59 53 57 45 70 64 99 64 93 55 47 67 79 55 76 57 71 73 65 92 87 62 55 61 62 77 58 46 60 72 58 53 69 65 57 60 46 63 62 74 49 69 47 43 42 51 46 36 33 48 27 57 42 51 38 53 36 67 30 46 33 35 33 33 52 29 30 37 37 38 36 40 38 24 30 34 41 29 37 25 31 38 45 47 35 33 55 35 39 39 45 39 51 45 32 42 36 46 48 33 28 35 42 43 36 36 38 36 28 46 31 40 61 36 29 36 46 69 31 38 34 32 39 39 75 32 47 42 46 40 55 51 56 49 84 49 63 47 43 48 53 59 59 37 60 60 46 57 53 54 51 43 50 42 37 25 40 52 42 46 30 40 37 35 33 18 30 43 35 39 43 45 39 38 36 30 42 25 33 26 24 47 46 34 34 17 28 29 44 27 32 28 29 32 28 8 23 15 21 22 27 22 31 22 18 20 15 31 28 22 26 18 18 23 27 21 20 25 18 27 32 35 25 48 32 29 24 20 21 13 24 26 17 13 30 26 25 18 31 25 25 20 31 25 23 38 26 29 31 23 13 35 36 46 41 46 39 27 27 32 30 23 25 39 22 23 36 28 27 37 18 19 23 16 20 17 30 15 20 8 17 24 16 15 9 14 20 15 9 20 21 16 11 21 24 18 9 13 24 21 16 20 15 15 22 14 21 17 9 15 15 14 17 13 12 20 14 19 10 17 13 15 23 9 18 13 11 9 14 7 8 13 18 14 9 14 7 22 25 15 28 21 19 11 19 15 16 9 11 15 11 11 14 15 20 12 13 17 10 14 17 6 19 10 16 16 23 17 20 21 27 16 27 14 28 32 31 20 16 28 21 25 15 18 14 15 19 16 23 14 12 17 16 14 18 21 11 12 15 13 11 11 17 14 18 14 13 17 15 7 14 10 10 11 13 6 11 15 14 11 16 17 11 6 11 16 9 9 15 6 7 7 11 7 11 11 11 7 19 9 11 9 14 5 9 14 5 4 4 7 4 12 7 8 15 7 14 8 11 19 5 7 9 15 14 10 8 5 5 8 8 6 14 10 8 5 7 9 11 7 18 11 7 12 11 9 11 10 14 14 4 9 14 5 8 8 12 6 9 12 8 8 8 5 5 5 9 11 7 6 3 7 8 8 6 4 11 6 8 7 10 8 8 6 7 10 7 9 8 8 5 8 5 7 4 5 6 9 8 11 7 11 10 10 11 9 12 11 6 6 10 8 11 14 11 1 10 4 6 12 6 2 10 10 14 12 5 14 6 2 8 10 9 10 7 10 5 7 9 13 6 8 4 1 4 4 8 7 11 10 11 16 8 9 5 7 10 7 7 11 10 14 9 6 10 10 3 5 7 7 4 11 7 10 10 13 10 12 4 4 10 9 3 12 10 6 17 13 14 12 11 15 12 10 6 7 19 64 118 114 155 121 82 72 58 22 4 5 6 7 6 11 7 8 7 11 8 2 10 8 12 5 7 3 7 7 2 8 6 15 10 10 11 7 14 9 18 13 8 13 10 4 10 2 3 5 9 11 10 13 12 7 6 9 9 7 7 5 3 5 5 3 5 11 9 2 2 11 10 2 1 12 5 5 13 9 16 6 6 8 22 23 3 7 7 9 11 4 12 10 5 11 9 5 9 10 17 5 10 8 15 16 7 1 3 4 6 8 4 1 6 6 3 6 8 8 3 7 2 5 8 3 9 9 9 8 6 8 5 5 2 3 6 6 3 11 4 4 10 2 4 7 5 6 0 9 9 10 3 3 1 3 8 4 9 10 6 8 2 9 3 9 5 6 6 1 6 3 1 5 9 3 5 6 6 8 8 7 5 10 3 8 6 3 5 6 6 3 3 3 8 5 12 3 5 5 8 10 10 3 6 6 7 1 3 4 10 5 4 9 3 5 4 2 9 8 3 2 7 10 5 4 7 5 2 3 2 4 10 3 12 3 4 3 0 6 2 2 6 8 4 5 15 7 4 5 5 5 3 8 5 6 4 6 4 7 6 3 4 5 6 8 8 5 5 6 2 2 10 5 3 3 3 5 7 3 1 4 5 6 4 7 2 2 12 6 13 3 3 18 5 10 7 10 1 7 8 5 4 7 3 4 6 3 4 5 7 8 8 6 11 10 10 10 6 7 10 4 3 8 
];
B = [
0 0 0
 47304 21558 25746
 20455 8673 11782
 79600 39828 39772
 49567 22419 27148
 26682 11382 15300
 75947 37004 38943
 59073 27158 31915
 33149 15395 17754
 99940 47440 52500
 98413 45494 52919
 17307 7719 9588
 285621 138957 146664
 35795 16027 19768
 10709 4651 6058
 64786 35504 29282
 19297 9591 9706
 5793 2780 3013
 67204 35054 32150
 5515 2688 2827
 4811 2140 2671
 1022 422 600
 30 13 17
 1001 418 583
 97491 51246 46245
 5873 2545 3328
 6924 3238 3686
 96846 49292 47554
 4697 2163 2534
 10238 4798 5440
 155810 78416 77394
 9266 4153 5113
 16390 7774 8616
 102005 51588 50417
 57714 29467 28247
 94469 48466 46003
 194595 100052 94543
 151596 73988 77608
 90246 45827 44419
 227399 117889 109510
 88419 41807 46612
 5943 2697 3246
 223525 114010 109515
 3226 1453 1773
 5708 2628 3080
 313987 165173 148814
 5576 2520 3056
 71428 33332 38096
 447865 247312 200553
 68965 32413 36552
 4 1 3
 3261515 1895643 1365872
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
19 15 0 0
21 14 0 0
47 6 0 1
75 15 0 0
84 8 0 0
157 10 16 0
279 23 24 5
409 31 33 10
1731 30 30 34
10551 67 65 73
30728 83 69 57
67401 86 81 57
135908 122 346 76
287081 150 610 114
466923 191 766 155
560099 298 314 293
463519 386 619 467
296717 479 710 600
161324 636 635 774
73041 864 704 932
24796 1073 891 926
5275 1303 1244 989
2052 1623 1104 910
1780 1475 1131 1226
1594 1831 1120 3497
1785 3552 1085 2073
3782 1661 1013 1016
1648 1267 975 1006
1725 2568 1169 1055
1297 1242 1338 1066
1347 1290 1202 1196
2996 1669 1254 1279
1738 1488 1253 1288
1828 2020 1382 1463
1850 1763 1583 1601
2006 1779 1752 1687
2118 1928 1897 1924
2412 2270 2125 2021
2463 2319 2348 2358
2675 2493 2477 2418
3168 3053 2860 2789
3258 3167 3226 3158
3495 3513 3688 3574
3890 4130 3995 4014
4449 4380 4410 4437
5037 5229 5157 5789
5682 5891 6060 5617
6190 6266 6185 6171
6870 6926 6933 6968
8041 7751 7309 7272
8263 8003 8157 8218
8693 8665 8594 8555
9362 9299 9150 10336
9914 9592 9566 9574
10808 10154 11726 10658
10634 10631 10923 10570
11038 11348 12826 11168
13916 12527 12406 11980
13079 11790 12368 12396
13979 13280 13128 13613
14194 15448 14176 14271
14179 13539 14938 13742
16148 13052 14843 14331
13365 12736 11903 13102
10732 13980 11609 9040
6631 9071 5712 6657
4173 5750 4522 4214
4423 6518 5474 3891
4469 3172 3080 2768
3191 2950 4715 2155
2073 1707 2146 2441
2652 1769 1986 1875
108 76 93 110
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
