A = [
15279 14038 26237 15715 15068 14839 14225 15057 15062 14915 15658 16098 17098 17662 18252 18223 18613 18658 19003 18563 18810 18899 18547 18970 19358 31409 31891 31750 43936 44502 47121 48230 48397 49960 50721 50411 50193 48863 49149 48296 48281 48132 48035 48524 48625 47749 46766 46911 45065 44523 44718 43951 44577 43882 43600 43860 43234 42704 41622 40753 40678 39927 39583 39706 38956 39610 38769 38545 37791 36409 35796 35071 35111 35019 34311 34225 33868 33466 32322 31962 31065 30618 30028 29625 29115 28945 28600 28068 27943 26952 26326 25557 25254 24510 24525 24061 23663 23806 23286 22898 21937 21647 21408 21104 20457 20411 19989 20061 19801 19414 18600 18250 17806 17700 17282 17087 17194 16888 16443 16419 15711 15726 15361 14929 14732 14607 14215 13867 13664 13352 13090 12888 12380 12444 12029 11944 11783 11711 11547 11196 10879 10992 10811 10443 10256 9676 9649 9603 9226 10422 9033 8626 8519 8264 8026 7859 7688 7467 7523 7319 7260 7081 6947 7047 6778 6749 7104 6612 6230 6097 5932 5637 5659 5548 5411 5290 5052 5018 5088 4685 4853 4581 4508 4641 4645 4328 4225 4158 4093 5522 4063 3632 3793 3643 3511 3408 3410 3274 3114 3035 3119 2997 2914 2930 2773 2767 2563 2547 2512 2557 2599 2465 2446 2248 2229 2245 2100 2123 2027 2007 1977 1848 1780 1794 1724 1733 1688 1623 1609 1590 1545 1511 1455 1358 1346 1241 1365 1301 1268 1293 1217 1153 1195 1187 1077 1113 1023 977 1049 963 957 945 965 921 834 867 759 762 764 769 731 671 725 686 649 626 638 617 580 543 560 552 547 529 497 492 479 511 426 472 397 446 406 427 387 399 361 349 373 316 358 334 352 323 311 305 328 286 255 284 275 248 279 240 232 223 208 194 220 222 182 200 212 197 190 187 185 150 166 188 154 150 136 147 109 137 148 142 121 123 115 130 126 109 114 105 117 112 100 90 112 105 84 95 97 97 93 88 93 94 100 90 69 55 70 71 72 78 83 64 78 58 67 55 57 49 64 53 59 39 47 59 61 49 47 51 49 45 49 42 53 49 46 42 41 36 41 33 39 33 14 27 26 32 29 33 30 27 25 25 30 34 38 24 18 30 35 32 24 27 20 28 24 27 25 37 28 29 29 17 21 31 26 27 25 27 23 18 21 23 20 18 21 19 22 20 23 17 26 19 22 19 21 28 17 21 9 14 16 22 12 22 16 24 14 18 23 10 15 15 13 15 25 15 14 14 15 10 16 12 19 12 17 15 20 5 18 13 9 12 16 15 11 18 12 12 16 13 17 16 11 10 13 23 9 12 8 15 10 7 16 11 19 12 10 13 8 11 11 19 18 18 13 13 8 17 16 9 8 12 15 9 9 17 8 10 15 10 13 9 8 12 9 9 12 9 9 16 11 12 11 5 10 11 8 7 9 16 8 9 10 8 7 22 10 8 9 9 10 10 12 15 10 8 14 8 14 5 8 6 9 9 5 11 4 8 5 10 8 8 9 13 12 10 11 6 12 9 13 7 6 8 11 13 9 5 15 12 13 6 7 5 5 7 6 13 8 4 2 2 4 4 8 2 5 6 9 9 5 6 10 8 10 6 4 8 8 6 7 10 3 7 7 6 6 8 13 4 10 8 4 6 2 6 12 7 10 8 6 5 8 10 5 7 2 4 2 8 4 3 11 2 11 5 7 5 3 1 2 3 8 11 5 8 2 5 6 6 5 5 4 5 6 5 1 1 5 1 5 12 5 4 7 11 3 2 6 10 9 6 7 13 3 2 2 11 6 9 8 2 10 4 6 3 9 6 6 3 5 5 6 5 2 5 4 5 4 5 8 4 1 6 5 7 7 5 7 2 1 5 6 3 2 3 9 0 1 6 5 5 6 7 8 4 6 7 3 1 1 4 4 2 4 4 1 5 3 2 4 1 6 7 5 2 5 5 4 3 6 5 1 3 5 3 3 6 2 7 2 2 3 3 1 3 4 5 1 2 2 3 6 3 6 7 1 5 2 1 0 4 2 3 3 4 1 5 4 3 1 6 0 2 3 3 3 3 2 2 5 2 3 6 3 6 2 3 2 0 4 6 2 2 3 2 3 5 1 3 2 5 1 1 2 2 5 1 4 2 3 3 3 5 5 1 2 3 3 4 5 7 3 0 4 3 2 1 4 1 3 3 1 1 6 0 4 0 2 2 1 4 3 1 6 3 2 2 0 0 2 2 3 1 1 3 1 2 2 2 0 2 1 2 0 1 1 1 6 3 3 2 2 1 2 3 4 0 0 0 2 0 2 0 0 1 1 1 1 3 3 3 1 1 2 0 1 2 1 3 2 1 1 3 2 0 1 0 0 1 1 3 3 1 5 6 1 3 1 4 0 0 2 1 3 3 0 1 3 3 0 1 4 1 2 1 4 1 1 1 3 1 2 4 1 0 1 0 0 1 1 1 3 3 1 0 1 2 1 1 1 1 1 3 2 1 0 4 1 1 4 0 3 1 1 0 3 1 1 0 3 1 1 2 0 2 2 1 1 1 2 1 1 2 3 0 1 1 2 1 0 0 2 1 1 1 2 0 0 3 0 0 0 1 1 2 1 2 1 1 1 1 2 2 0 1 0 0 2 1 1 1 1 2 2 2 0 1 1 4 1 3 2 0 1 0 0 0 2 1 0 1 0 1 1 1 1 2 0 2 1 0 0 1 0 0 0 0 0 1 0 1 2 1 1 0 0 0 3 1 0 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 2 1 0 3 0 0 0 2 1 1 4 2 0 4 0 0 0 2 2 0 0 1 0 1 0 0 3 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 2 1 0 0 0 1 1 1 0 2 0 1 2 0 1 0 0 2 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 0 0 1 2 1 2 3 2 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 1 0 2 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 2 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 2 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 3 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 2 0 0 0 2 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 2 0 0 0 0 0 0 0 1 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 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 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 0 0 0 0 0 1 0 0 0 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 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 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 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 0 0 0 0 0 1 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 1 0 0 0 0 0 0 0 0 0 0 0 
];
B = [
0 0 0
 18539 15123 3416
 9191 7390 1801
 25209 21162 4047
 20463 16892 3571
 11274 9207 2067
 28958 24100 4858
 16070 13278 2792
 22336 18620 3716
 34530 28762 5768
 15338 12889 2449
 47065 39701 7364
 34383 29368 5015
 9890 8403 1487
 17089 14609 2480
 15317 13017 2300
 3243 2708 535
 25302 21847 3455
 4802 4123 679
 1949 1661 288
 968 812 156
 494 403 91
 325 272 53
 36877 31491 5386
 6796 5752 1044
 3332 2827 505
 39077 33502 5575
 8343 7070 1273
 2849 2434 415
 59349 50898 8451
 10866 9288 1578
 5217 4448 769
 41782 35627 6155
 8971 7630 1341
 36718 31341 5377
 19886 17113 2773
 13073 11249 1824
 64522 55224 9298
 28030 24234 3796
 26322 22739 3583
 68205 58316 9889
 39841 34541 5300
 40331 34466 5865
 54027 46663 7364
 43347 37463 5884
 42641 36724 5917
 72743 63033 9710
 80999 70294 10705
 31581 27692 3889
 160777 140255 20522
 88160 77157 11003
 113678 99997 13681
 170072 149309 20763
 224107 197719 26388
 1 1 0
 225692 200241 25451
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 0 0 0
3 0 1 0
14 2 9 0
136 0 12 3
961 1 32 7
4115 3 42 26
11789 3 61 40
31275 1 88 54
64121 9 129 107
110558 27 203 180
138976 64 281 314
130509 122 419 416
84489 158 615 581
38185 170 806 792
12340 280 1101 1100
3566 394 1348 1464
2137 692 1928 2206
2306 947 2400 2227
3582 1526 2662 2427
2894 2104 2659 2893
2762 2612 2967 3651
3953 3348 4515 3922
3544 4941 4821 4120
4996 5724 5089 5528
5748 6192 6432 6285
7406 7429 6349 8393
6292 9023 7471 7121
6736 8569 8252 7675
8156 10099 7926 9073
7623 9902 8683 8383
7663 10773 9465 9727
8496 9569 8263 7806
5446 7662 7578 7097
5734 6381 5930 5830
5515 6165 5703 5824
5476 6061 5814 5773
5788 6034 5896 5729
5708 6030 5923 6010
5689 5876 5860 5924
5893 6158 5882 6005
6257 6160 6344 6274
6361 6503 6478 6567
6745 6861 6989 6852
7198 7135 7093 7131
7584 7683 7700 7641
8115 8116 7949 8055
8281 8378 8214 8310
8781 8729 8633 8725
8857 8820 8837 9029
8961 9080 8925 9000
8904 9145 9115 9096
8571 8705 8700 8684
8434 8312 8278 8285
7836 7876 7588 7784
7065 7339 7273 7153
6481 6477 6588 6595
5828 5834 5931 5876
5129 5256 5250 5329
4611 4520 4664 4712
4030 4085 4157 4126
3747 3810 3695 3687
3661 3629 3673 3693
3528 3500 3481 3500
3337 3440 3286 3443
3380 3191 3204 3269
3267 3219 3087 3294
3178 3199 3106 3110
3036 3153 3018 3005
2793 2761 2743 2756
2501 2454 2416 2412
2106 2125 2086 2077
1686 1746 1673 1660
1167 1186 1297 1227
869 845 939 874
627 657 706 678
467 460 437 501
251 239 242 241
102 97 106 97
6 5 5 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
