A = [
20010 19834 108642 21845 19666 18057 18596 17829 18685 18181 20371 23863 28604 34075 42919 49587 53068 55525 57216 56040 53150 50786 49745 47991 47712 50651 47984 45547 45217 37808 37177 34322 23367 23373 23207 22891 22315 21941 21814 21623 21462 21955 21641 22247 22375 22514 22234 21976 22516 22339 21767 21918 22217 22290 22122 22331 21682 21806 21879 21128 20901 21050 21016 20911 21034 21249 20804 20815 20684 20600 20722 21029 20915 21204 21426 21275 21498 21030 21132 20692 20357 20023 19723 19637 19661 19579 19098 18941 18562 18429 18428 18584 18200 18263 18039 17919 18047 17843 17814 17289 17488 17334 17236 17227 17218 17109 17112 16921 17039 16756 16441 16266 16499 16278 16214 16051 16121 16176 16112 15935 15890 15885 15957 15931 15552 15249 15589 15198 15255 15316 15163 14920 14900 14725 14968 14887 14610 14749 14627 14487 14420 14287 14350 14159 14136 13987 14114 14014 13918 13857 13953 13700 13796 13525 13473 13210 13443 13148 13343 13308 13240 12924 12804 12845 12710 12647 12778 12580 12522 12474 12404 12308 12308 12215 12098 12134 12239 12139 12084 11763 11963 11799 11874 11782 11693 11785 11599 11399 11645 11751 11371 11383 11388 11324 11164 11021 10919 11072 10946 11075 10814 10754 10713 10771 10739 10841 10613 10485 10487 10539 10444 10462 10196 10200 10073 10002 9832 9728 9914 9898 9967 9803 9666 9761 9807 9646 9640 9514 9284 9274 9174 9061 9274 8759 8836 8800 8799 8743 8725 8678 8568 8418 8299 8405 8475 8362 8348 8218 8153 8047 8006 8016 7942 7911 7823 7771 7813 7840 7817 7614 7506 7219 7319 7449 7354 7360 7171 7036 7110 7018 6962 7176 6858 6769 6875 6796 6653 6583 6665 6705 6656 6529 6682 6500 6485 6349 6473 6408 6343 6364 6294 6251 6287 6275 6174 6259 6141 5985 5960 5936 5895 5798 6001 5948 5792 5718 5763 5592 5731 5708 5633 5712 5677 5481 5538 5520 5400 5315 5435 5413 5300 5282 5242 5275 5305 5309 5152 5099 5162 5131 5104 5095 5171 5048 5064 5024 5126 5056 4951 4953 4965 5054 4898 4801 4745 4747 4737 4785 4698 4655 4716 4670 4671 4621 4593 4453 4577 4563 4468 4358 4414 4387 4134 4097 4175 4114 4080 3987 3989 4074 3911 3746 3817 3635 3669 3571 3598 3548 3580 3436 3486 3413 3318 3319 3321 3225 3196 3101 3046 3128 2959 2925 2972 2857 2795 2573 2655 2596 2512 2543 2498 2316 2387 2361 2372 2353 2216 2305 2115 2132 2081 2021 1931 1914 1809 1796 1733 1684 1583 1576 1592 1665 1461 1451 1447 1340 1390 1393 1351 1256 1206 1208 1156 1145 1134 1102 1094 1091 998 995 982 917 953 851 849 878 792 791 783 730 730 701 707 642 628 602 626 604 577 607 525 541 539 513 539 496 471 463 486 422 405 417 416 400 349 369 324 336 309 321 296 316 289 285 279 308 293 242 252 241 237 253 224 229 198 252 237 222 196 191 174 179 166 163 180 170 163 164 141 115 111 144 113 118 118 109 98 96 97 84 76 75 68 77 59 69 80 87 77 50 51 53 47 78 58 52 47 49 49 46 41 50 39 44 33 40 39 28 39 40 35 38 27 33 36 32 38 27 36 23 29 28 27 31 45 33 36 35 40 41 26 28 27 25 38 28 28 36 39 32 37 39 20 39 28 18 14 19 45 18 20 27 28 22 23 24 20 22 15 19 25 19 17 29 34 17 34 17 14 13 15 18 9 15 29 30 13 21 15 12 9 12 16 10 3 7 6 9 11 11 9 11 15 19 16 21 14 23 10 8 16 17 7 8 5 8 9 6 7 6 10 4 3 13 6 3 3 7 6 6 9 9 6 8 5 4 2 12 8 5 6 11 11 5 5 8 4 6 8 2 6 4 9 5 9 11 3 4 7 7 8 3 4 9 5 2 5 2 8 3 7 6 6 7 10 7 6 6 2 5 8 6 8 7 9 3 7 5 2 3 7 3 4 3 6 6 6 7 6 6 4 1 9 20 22 32 18 15 24 20 22 19 11 6 16 6 26 16 6 10 14 30 25 13 12 25 7 14 12 10 11 6 8 4 9 3 6 7 7 9 2 4 3 16 12 14 4 14 4 14 22 6 9 4 1 2 6 6 3 8 1 10 9 13 9 30 10 5 14 10 20 14 10 5 10 18 18 5 8 6 31 6 6 17 16 11 10 6 4 5 5 13 7 4 9 3 4 2 0 4 5 1 2 3 1 5 3 10 3 2 6 1 4 4 6 6 5 4 3 2 4 4 2 10 7 18 4 4 10 30 13 3 18 18 8 14 15 8 2 4 15 1 5 10 14 22 9 12 13 2 5 10 6 7 17 16 17 12 10 16 10 4 10 17 15 13 6 10 14 12 15 8 12 14 22 19 20 26 31 24 16 11 20 18 19 15 13 16 13 16 17 19 19 15 25 17 11 11 4 21 23 18 6 18 33 18 6 14 10 18 14 12 8 9 16 14 15 17 16 18 22 11 16 10 15 19 17 13 13 18 20 11 9 9 16 16 11 2 16 13 22 19 14 9 10 4 9 11 2 15 10 13 1 6 9 17 10 13 6 12 14 8 10 5 13 16 11 13 5 14 13 21 9 6 16 16 15 10 10 15 14 17 14 5 13 9 11 15 10 17 14 13 9 10 9 2 2 3 3 3 2 2 0 0 5 2 4 1 2 1 3 3 1 3 0 4 4 3 1 7 5 7 4 5 3 3 6 0 2 2 4 6 0 1 1 3 3 2 2 2 2 3 1 2 0 2 3 2 4 1 3 2 2 0 0 2 2 4 2 1 2 3 1 1 1 1 4 2 1 4 0 0 0 1 6 5 10 6 5 12 6 4 8 9 11 9 5 7 5 9 5 7 8 4 8 5 8 6 12 22 13 20 14 5 11 15 13 14 11 17 14 8 17 9 9 8 17 2 4 3 4 1 4 4 2 1 2 13 0 2 0 4 0 1 2 1 1 1 2 1 4 2 3 1 1 1 1 0 0 2 0 1 1 2 1 2 1 0 0 3 2 1 3 4 5 1 2 2 2 1 1 3 2 1 0 2 2 3 0 1 1 2 1 3 3 1 0 2 0 1 0 3 2 2 3 0 2 0 0 2 1 1 3 0 2 0 2 1 0 2 2 1 0 0 1 2 2 3 4 3 6 3 1 3 2 1 5 2 4 1 0 1 3 2 3 4 1 8 3 7 3 5 4 4 4 4 9 10 2 6 1 6 3 3 2 1 7 3 4 5 3 0 7 8 3 3 3 5 4 2 2 3 6 0 4 2 1 3 2 4 1 4 8 1 5 3 2 1 3 1 6 4 3 2 0 1 6 2 1 0 1 1 4 2 1 1 0 1 1 1 4 0 0 0 1 0 1 1 0 1 1 0 1 2 3 1 5 1 2 1 1 0 1 3 0 1 0 1 1 2 0 1 0 0 1 1 0 2 4 1 1 0 0 2 1 1 0 2 0 1 2 0 0 1 0 3 0 2 2 0 1 0 1 1 0 2 1 1 1 0 0 1 0 1 0 0 2 0 1 0 0 1 0 0 1 0 0 1 1 1 9 0 0 0 0 1 1 0 5 1 4 5 2 0 5 2 1 2 4 1 1 2 2 4 1 1 0 2 3 2 1 5 1 2 1 0 1 1 3 1 1 5 5 3 2 2 1 2 5 3 2 4 3 10 4 4 1 1 5 0 4 2 2 5 7 3 5 3 3 3 3 5 2 5 1 1 0 4 7 4 1 6 3 3 7 4 4 3 8 0 2 0 4 4 3 6 7 3 8 5 2 3 4 4 1 4 1 2 1 2 2 2 5 8 2 6 6 1 10 13 8 4 9 2 1 6 4 3 2 13 7 0 4 1 5 7 2 9 4 3 3 10 5 6 13 6 5 5 2 3 4 0 5 1 5 11 4 2 14 11 6 5 4 1 1 6 3 3 0 2 3 4 6 4 14 6 8 9 7 12 8 1 3 0 6 12 1 2 6 11 9 2 3 0 4 7 3 2 8 0 7 5 5 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 2 0 0 0 1 2 0 1 1 3 1 4 0 0 1 3 2 1 2 1 1 0 4 1 0 0 2 2 1 0 2 3 1 2 2 3 1 0 1 1 3 1 1 1 2 3 3 2 2 3 5 5 1 1 5 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 2 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 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 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 2 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 2 1 0 1 0 1 4 0 1 0 2 0 0 2 0 1 0 0 3 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 
];
B = [
0 0 0
 13174 10036 3138
 21683 17611 4072
 12543 10060 2483
 41118 33591 7527
 16394 13626 2768
 9529 7922 1607
 9751 7933 1818
 5838 4708 1130
 4637 3738 899
 2705 2187 518
 5670 4600 1070
 6124 5040 1084
 4455 3727 728
 28974 24409 4565
 8916 7514 1402
 10835 9341 1494
 7273 6310 963
 9543 8007 1536
 9672 8172 1500
 6395 5438 957
 21023 17761 3262
 11159 9358 1801
 11425 9682 1743
 7342 6317 1025
 11500 9829 1671
 10947 9463 1484
 17415 14761 2654
 7616 6551 1065
 12073 10235 1838
 12233 10438 1795
 7500 6509 991
 12673 10949 1724
 11721 9949 1772
 16283 13915 2368
 8253 7143 1110
 12582 10749 1833
 18544 15858 2686
 12218 10531 1687
 8623 7497 1126
 17473 15054 2419
 15054 12883 2171
 16833 14474 2359
 7819 6802 1017
 13304 11504 1800
 16739 14384 2355
 8832 7746 1086
 16705 14430 2275
 13904 12000 1904
 16649 14275 2374
 8730 7649 1081
 16542 14180 2362
 14017 12031 1986
 16904 14544 2360
 7997 7006 991
 18341 15743 2598
 16169 13908 2261
 7245 6359 886
 16430 14083 2347
 11702 10076 1626
 2021110 1781854 239256
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 1 0 0
1 2 0 0
0 0 0 0
1 2 0 0
0 2 0 0
5 3 0 0
18 5 1 0
28 3 10 2
70 4 16 7
90 2 21 14
77 10 29 16
135 23 55 40
745 55 88 65
6898 70 133 135
104555 143 207 240
419340 252 411 447
173243 417 693 710
11059 543 1008 981
1812 803 1474 1375
2061 1146 1718 1789
2275 1567 1988 2036
2501 2222 2388 2536
3221 2631 2862 2898
3290 3195 3328 3351
3964 4876 3865 3754
4570 4407 4189 4150
4848 5000 4671 4761
5331 5450 5241 5165
5805 5867 5706 5610
6306 6487 5922 6267
6982 7029 6690 6655
7262 7399 7125 7185
8254 7475 7581 6952
7793 7925 7338 7892
7449 7493 7378 7586
7986 7750 7870 7693
8000 8070 8187 8252
8292 8483 8185 8459
8738 8909 8563 8673
9116 9050 9126 9018
9647 9357 9626 9616
9938 10002 10072 9983
10401 10703 10477 10686
10861 11092 11119 10913
11417 11355 11399 11341
11872 11681 11744 11822
11945 11855 12099 12166
11830 12301 12055 12069
11984 12042 11876 12125
11741 11599 11724 11786
11113 11270 11188 11125
10834 10565 10758 10823
9737 10071 10066 9961
9246 9378 9230 9235
8512 8330 8317 8495
7580 7677 7642 7756
6974 7205 7018 7137
6528 6583 6603 6625
6144 6175 6201 6104
5876 6022 5993 5806
5982 5757 5858 5804
6046 5963 5961 5992
6380 6343 6315 6258
6592 6592 6567 6655
13159 13535 9119 9158
7770 7748 7717 7716
8295 8183 8136 8254
8426 8358 8375 8293
8452 8397 8277 8578
8023 7940 7944 7868
6776 6942 7043 6923
5684 5770 5705 5897
4485 4626 4474 4586
3512 3404 3448 3522
2414 2406 2403 2474
1772 1823 1739 1710
1238 1208 1195 1149
776 763 812 792
521 511 537 535
39 55 42 56
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
