A = [
16626 16336 288067 16435 13320 12438 12659 11154 11137 10997 12312 15263 18072 20932 24928 27864 29604 31692 32853 33495 33829 34251 34671 34830 35413 38193 36837 35678 36944 31014 30015 28517 20636 20474 19867 19358 19136 18721 18256 18073 18100 17986 18080 17783 18069 17684 17745 17735 17501 17376 17478 17148 17653 17198 17384 17014 17143 16821 16957 16665 16655 16773 16747 16863 16762 16482 17231 18612 17480 18302 18630 18978 19249 19028 19003 18765 19395 18864 18583 18144 17975 17956 18320 18317 18414 17989 19920 17880 17720 17908 17498 17342 17600 16859 17800 16820 17996 16871 16568 16931 16416 16495 15751 15514 15608 15513 15743 15489 15204 14979 14948 14800 14777 14562 15040 14280 14235 14299 14190 13929 13769 13686 13688 13500 13470 13519 13576 13145 12823 13184 12963 12698 12526 12586 12312 12389 12103 12103 11993 12014 11895 11733 11730 11333 11204 11317 11327 11263 11055 10888 10836 10767 10520 10335 10409 10180 10184 9911 9860 9891 9960 9722 9785 9503 10384 10005 10332 10012 10484 10790 11487 10371 10169 9965 10129 11618 9769 9012 9488 9876 10849 10147 9513 10172 9941 9161 9772 9212 9020 9496 8538 9825 8707 7613 6493 6184 6286 6189 6055 6002 5747 5860 5648 5532 5656 5335 5440 5220 5368 5153 5130 5111 5036 4873 4867 4818 4631 4853 4701 4408 4307 4477 4309 4243 4415 4165 3957 4046 4004 4042 3773 3695 3829 3478 3539 3503 3422 3358 3243 3394 3235 3113 3202 3130 3007 3067 3053 2944 2896 2906 2841 2858 2717 2872 2705 2637 2549 2504 2727 2551 2468 2477 2543 2645 2601 2633 3076 3015 2891 3023 3199 3047 3235 3183 3280 3420 3316 3153 2637 2537 3271 2604 2779 2001 2578 2591 2234 2646 2146 2048 1964 1564 1483 1600 1451 1452 1424 1426 1374 1326 1285 1198 1176 1227 1186 1146 1129 1082 1054 1100 1052 985 1025 989 1037 997 994 1017 960 922 934 993 895 896 894 897 836 898 903 848 1459 1170 737 726 729 687 704 669 724 673 617 674 705 646 617 574 586 547 588 544 507 582 545 537 577 515 493 512 507 566 533 566 564 615 546 592 580 537 507 514 457 526 507 442 599 457 424 496 444 463 363 398 403 441 438 379 482 447 374 413 348 395 355 380 388 390 378 299 291 282 292 327 285 250 243 273 248 209 236 222 203 252 226 198 217 194 174 211 205 201 184 229 161 196 215 227 196 207 211 212 474 428 226 190 180 172 161 173 249 169 171 183 172 150 170 174 170 160 198 172 160 171 164 155 158 175 145 153 155 185 153 144 170 172 155 174 154 193 184 153 141 144 130 158 151 150 158 136 132 143 145 156 153 138 122 144 122 99 130 115 100 113 121 111 126 124 98 107 91 85 88 100 87 93 102 104 102 97 78 104 87 90 100 71 95 86 93 77 88 72 95 88 80 82 67 65 90 85 89 77 91 92 81 72 88 89 67 100 85 95 75 94 83 89 89 107 78 133 93 87 64 92 73 60 66 60 79 66 73 66 70 56 64 52 55 65 58 68 69 54 43 62 47 68 46 61 58 64 58 67 48 51 59 37 48 48 53 50 49 66 59 67 57 50 58 67 59 67 45 53 47 49 55 42 48 57 47 49 55 54 40 63 42 55 43 47 50 53 49 45 37 54 47 54 36 57 39 62 54 54 40 59 51 48 57 67 69 63 44 56 50 72 92 63 83 76 76 75 76 71 58 64 60 51 55 50 53 45 34 40 39 45 38 39 21 40 30 33 43 28 38 31 36 28 37 34 37 41 27 38 41 35 38 33 32 28 39 30 36 34 24 37 32 30 33 23 35 42 19 24 31 25 26 24 36 29 27 32 34 29 27 18 27 29 27 29 25 25 28 33 20 32 24 24 36 27 38 33 22 23 27 32 28 29 28 30 27 22 26 24 26 36 29 25 29 27 28 24 33 22 24 35 34 39 34 32 28 22 24 28 33 25 23 25 20 25 25 19 29 21 23 25 29 24 25 20 23 23 34 61 82 92 107 120 89 108 114 150 134 136 127 135 284 199 172 195 204 113 289 558 514 644 781 686 681 511 453 699 1575 734 530 1729 545 203 368 182 79 85 73 62 65 242 65 28 47 47 27 36 25 36 59 51 41 39 32 67 32 12 26 19 18 13 16 22 14 20 16 18 20 18 25 26 23 22 22 27 17 24 14 12 35 32 22 40 8 15 18 13 18 9 9 9 15 27 10 13 17 14 17 34 39 51 39 45 63 63 64 89 90 99 93 146 169 198 180 165 314 281 847 1037 852 1067 884 641 856 685 784 794 645 891 870 861 780 392 357 495 119 79 56 88 87 123 147 125 176 198 156 225 447 192 164 479 198 108 163 108 181 172 123 149 118 389 90 74 116 199 76 83 90 126 187 97 89 66 68 93 21 33 21 23 54 24 23 19 15 14 15 15 21 16 21 12 18 12 19 13 12 25 14 9 9 15 18 16 22 19 15 25 12 15 38 44 20 25 17 26 27 22 41 28 31 31 33 39 26 36 30 36 29 50 32 23 39 60 54 49 77 65 69 90 83 78 125 113 211 191 205 248 174 227 277 250 252 194 185 196 242 162 119 168 153 155 211 168 178 201 179 164 135 80 142 265 101 116 87 91 71 49 39 43 37 35 48 42 17 24 19 21 17 17 19 23 34 23 18 11 19 18 14 24 9 1 4 5 7 7 7 7 8 1 6 10 7 8 5 7 9 3 10 4 6 5 7 8 5 6 6 7 8 12 5 7 7 11 5 2 1 6 10 12 21 12 11 5 4 8 11 8 11 7 7 3 10 15 6 9 9 13 10 11 18 12 12 5 7 4 7 4 7 5 2 2 4 4 1 2 2 5 3 4 9 5 3 2 1 4 5 5 2 2 3 3 0 4 3 2 3 6 5 4 2 4 1 2 7 4 6 2 9 1 4 4 0 3 1 10 2 5 6 1 1 1 4 3 6 5 2 6 2 5 3 5 4 3 8 2 4 3 1 2 4 5 4 5 2 3 5 4 1 1 8 4 6 8 5 4 6 11 5 6 2 6 7 7 6 9 6 4 5 2 2 8 1 3 1 1 2 4 1 3 2 3 0 1 3 2 1 2 1 4 4 2 3 1 3 1 1 5 2 1 6 3 4 0 2 1 4 3 4 2 2 5 1 3 2 0 3 2 5 3 1 7 2 4 3 7 9 4 2 6 2 3 2 4 6 1 3 1 2 1 3 4 2 4 3 1 2 1 3 4 3 2 1 2 3 2 2 2 1 0 2 1 2 0 3 5 1 0 2 1 1 1 2 3 2 2 0 2 2 2 1 3 2 2 3 1 1 4 0 1 1 1 0 2 1 1 3 2 1 1 2 3 2 2 1 2 2 3 2 2 0 2 2 0 1 0 5 0 4 0 0 5 0 2 1 4 3 4 6 2 7 1 2 3 1 4 9 4 2 2 1 1 1 0 0 1 1 1 1 5 1 2 3 1 3 1 1 1 0 0 3 0 0 0 2 2 0 1 2 0 1 0 1 0 3 1 0 1 1 0 0 3 0 2 2 0 1 1 1 2 1 1 1 1 0 0 5 1 1 0 5 1 0 0 0 1 1 0 2 1 1 2 2 2 1 0 2 1 1 1 1 2 1 4 0 0 2 0 3 1 0 1 0 0 2 2 5 0 1 1 0 0 0 2 5 0 1 0 3 0 0 2 1 1 1 2 0 0 0 0 2 1 0 0 2 1 0 0 2 0 0 2 0 1 0 1 0 1 2 0 0 1 0 0 2 1 1 3 1 1 0 0 3 1 1 0 0 1 0 1 1 2 3 1 0 1 0 2 1 0 0 0 1 3 1 2 0 0 2 0 0 0 1 2 1 0 0 1 2 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 2 3 0 1 0 0 0 0 0 0 2 0 1 0 1 0 0 0 2 1 0 0 2 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 2 1 0 0 0 0 0 1 0 1 0 2 1 0 0 3 1 1 0 0 0 1 1 0 1 2 0 0 1 1 0 1 1 0 0 1 2 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 1 0 0 1 0 2 0 0 2 0 0 0 0 0 0 1 3 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 2 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 2 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 
];
B = [
0 0 0
 22747 8546 14201
 32509 10697 21812
 33168 9021 24147
 36394 20373 16021
 20681 11097 9584
 10106 5658 4448
 9176 5332 3844
 6109 3435 2674
 4514 2920 1594
 2834 2015 819
 4981 3457 1524
 6123 3984 2139
 5610 3255 2355
 18040 14518 3522
 7626 5464 2162
 9495 7369 2126
 6262 4973 1289
 6513 5347 1166
 6341 5247 1094
 4994 4042 952
 10150 8594 1556
 6946 5837 1109
 6864 5758 1106
 5268 4374 894
 6652 5626 1026
 6471 5423 1048
 8968 7676 1292
 5123 4306 817
 7053 5977 1076
 7188 6069 1119
 5852 4884 968
 7301 6188 1113
 7255 6105 1150
 9420 8037 1383
 6353 5375 978
 8089 6915 1174
 15518 12853 2665
 7389 6245 1144
 7797 6528 1269
 14485 12115 2370
 9065 7672 1393
 13657 11425 2232
 6943 5859 1084
 9148 7749 1399
 14190 11856 2334
 8221 6962 1259
 13723 11395 2328
 9477 8047 1430
 13872 11651 2221
 8483 7181 1302
 13739 11469 2270
 10519 8922 1597
 13939 11700 2239
 8903 7521 1382
 15004 12655 2349
 14005 11791 2214
 8790 7444 1346
 14144 12027 2117
 8500 7360 1140
 1436206 1287465 148741
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0
18 0 0 0
332 0 0 0
2106 4 1 0
6264 0 4 6
17715 5 17 9
43720 2 19 5
91881 3 30 14
148102 13 42 25
184976 26 60 62
159454 44 140 122
105372 82 196 194
45844 120 287 265
13211 174 407 404
2728 295 515 516
1024 417 637 660
940 636 817 817
1027 782 1349 1344
1228 1028 2215 2335
1389 1192 1265 1400
1597 1530 1561 1478
1846 1844 7420 9210
2280 2040 2049 2049
3571 3583 2385 2387
2613 2631 3120 3120
2876 2897 2695 2762
3278 3014 3013 3148
3244 3323 3390 3320
3418 3378 3456 3537
3730 3671 3709 3549
3650 5312 3750 3742
3960 4102 3973 3838
4016 4099 4089 3983
4222 4321 4194 4238
4559 4366 4335 4305
4660 4469 4624 4493
4742 4750 4829 4748
5119 5023 5050 5159
5306 5368 5295 5350
5671 5720 5660 5647
5679 5812 5979 5871
6165 5882 5993 6061
6340 6385 6310 6322
6353 6227 6391 6358
6352 6454 6362 6365
6170 6156 6192 6315
6076 6158 6124 5961
5668 5721 5726 5705
5366 5521 5455 5320
4810 4905 4767 4799
4317 4396 4366 4447
4004 4098 3973 4019
3500 3587 3594 3546
3267 3244 3346 3282
2961 3007 3048 2978
2901 2781 2733 2817
2756 2672 2746 2687
2699 2602 2661 2737
2731 2603 2619 2742
2885 2817 2955 2910
3026 3133 3026 3067
3235 3313 3381 3397
3724 3782 3816 3790
4080 4032 4282 4117
4563 4628 4519 4522
4873 4780 4733 4850
5187 5166 5108 5115
5269 5310 5234 5282
5348 5379 5271 5248
4942 4860 5067 4944
4413 4345 4283 4348
3283 3338 3246 3301
1810 1844 1856 1810
647 677 700 630
101 129 109 113
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
