A = [
46130 45326 242363 38601 36677 34857 32968 32198 31593 29944 29577 28692 28330 27662 27362 27151 26834 26057 26087 26098 25606 25772 25278 25523 25564 33622 33492 33895 42223 42344 43038 43360 43809 44005 44885 44642 44176 43094 43281 42029 42460 42311 42012 41966 41999 41490 40920 40419 40160 39767 39732 40148 39312 39258 38419 38822 38282 38286 38007 37044 37548 37026 36975 37155 36584 36496 36663 36088 35945 35509 34978 34583 35097 34167 34085 34529 33779 33352 32984 33033 32614 32090 32407 31666 31577 31308 30972 31297 30454 30630 30076 30206 29623 29450 29309 29289 28635 28950 28648 28265 28253 28244 27899 27734 27537 27297 27316 27104 26538 26687 26473 25815 25562 25566 25588 24642 24953 24731 24586 24552 24233 24283 23736 23373 23392 23052 23216 22729 22453 22247 21988 22165 21934 21504 21587 21329 20988 20682 20645 20522 20458 20117 20257 20026 19740 19389 19337 19288 18856 19034 18995 18862 18484 18679 17913 18004 17837 17895 17877 17476 17484 17226 16658 16677 16658 16378 16442 16335 16005 15881 15701 15601 15342 15205 15156 14993 14726 14732 14561 14416 14515 14228 13974 13768 13723 13570 13798 13472 13422 12922 13179 12911 12807 12700 12690 12458 12310 12124 12209 11741 12110 11538 11684 11303 11198 11282 11124 10794 10978 10905 10805 10686 10406 10300 9855 10179 10007 9891 9656 9609 9574 9450 9488 9051 8875 8782 8849 8809 8394 8335 8518 8367 8095 8338 7918 7908 7745 7704 7377 7365 7412 7338 7306 7261 7191 6920 6925 6841 6855 6695 6728 6498 6426 6410 6226 6271 6253 6123 5986 5846 5863 5868 5772 5629 5605 5309 5388 5187 5342 5192 5100 5008 5042 5033 4966 4787 4624 4739 4711 4480 4678 4496 4476 4502 4506 4432 4213 4113 4265 4091 3921 3945 3862 3816 3695 3757 3600 3625 3574 3580 3548 3391 3460 3580 3351 3196 3315 3165 3203 3112 3067 2976 3038 2864 2933 2916 2813 2696 2715 2685 2663 2426 2432 2383 2374 2333 2347 2180 2175 2145 2145 2062 2091 1967 1978 1931 2064 2106 2056 2035 2036 1928 1925 1932 1831 1764 1720 1679 1654 1581 1548 1925 1578 1541 1643 1561 2090 1528 1523 1556 1503 1466 1429 1421 1270 1349 1268 1237 1244 1239 1206 1153 1185 1130 1077 1184 1127 1094 1016 995 1001 1011 924 985 1039 914 909 902 966 919 991 873 1031 991 1018 990 945 830 845 818 831 835 781 867 921 957 844 748 644 720 652 668 653 672 672 639 638 594 621 518 526 511 531 541 510 504 500 462 511 627 502 421 499 428 486 520 503 498 471 400 315 377 393 392 356 363 388 356 371 366 317 396 314 297 359 310 331 302 297 270 299 255 262 295 314 328 301 321 277 292 383 314 320 311 255 236 210 205 230 214 216 221 219 217 230 249 223 212 224 196 218 196 213 218 212 198 203 193 205 188 206 190 212 237 195 205 208 185 174 164 165 160 174 177 189 162 168 159 139 169 130 128 132 169 139 154 156 138 134 160 167 165 149 144 141 176 142 246 229 230 235 225 253 301 250 404 313 463 328 279 343 272 252 230 270 297 232 208 198 257 192 275 175 241 201 118 106 96 110 94 135 127 148 181 175 208 196 204 155 155 150 155 122 193 175 116 143 137 129 146 127 132 139 175 158 140 115 120 139 119 86 86 93 88 81 88 79 81 77 93 89 79 72 79 88 79 73 80 100 81 67 74 79 90 66 77 70 58 65 93 80 71 77 89 82 79 77 82 71 58 77 74 74 62 47 62 61 64 50 49 65 62 49 80 69 62 64 49 58 55 59 63 48 50 73 65 68 48 65 64 38 55 51 58 51 51 51 39 35 38 52 53 54 54 57 48 46 56 65 45 47 62 48 54 58 35 51 49 39 36 44 47 38 43 50 39 57 60 38 48 55 45 35 37 34 33 37 41 50 47 41 56 51 49 45 62 41 45 56 43 57 62 62 88 167 212 203 142 160 196 124 97 139 194 101 102 219 128 128 137 150 192 144 100 59 76 71 74 33 39 44 35 34 38 49 34 47 45 46 53 94 70 62 93 73 71 53 88 68 53 48 68 64 74 64 66 97 91 39 23 32 27 37 32 40 30 42 25 45 39 47 33 40 51 52 23 39 37 70 28 34 28 23 39 20 24 33 19 33 31 37 34 29 23 16 41 29 31 28 34 35 22 26 26 32 31 39 43 36 26 38 37 40 26 26 24 31 29 31 34 26 22 30 27 38 34 29 18 27 17 28 18 16 16 15 21 21 22 32 14 27 23 30 24 18 26 26 24 33 22 26 32 21 22 24 27 29 24 37 21 20 31 24 27 27 19 32 14 27 20 16 26 14 15 17 15 27 18 30 19 16 19 16 15 26 26 26 31 38 44 48 21 27 26 30 26 29 23 23 13 23 30 15 24 23 12 14 24 23 18 12 23 12 26 18 13 20 22 20 7 15 14 9 17 15 12 17 15 15 16 12 8 10 17 20 11 15 11 13 17 8 10 10 12 15 9 11 16 11 7 16 11 11 10 19 18 10 9 20 16 12 13 10 12 15 15 19 12 16 18 12 24 10 15 12 11 12 18 13 16 6 15 13 9 13 5 8 16 12 8 15 9 12 13 7 9 15 12 8 15 13 13 11 9 12 8 12 9 7 16 13 13 5 11 6 6 10 15 14 9 14 12 10 18 10 10 9 18 11 9 9 10 15 12 19 14 12 10 11 7 10 4 14 7 10 14 17 16 11 10 8 15 8 5 8 15 6 10 9 7 10 8 8 9 9 4 7 10 9 3 12 9 14 6 7 7 10 8 8 4 9 6 3 4 9 8 5 5 7 6 8 12 6 8 9 7 9 10 4 6 6 10 8 10 15 9 4 7 8 8 5 13 5 9 6 7 9 9 8 7 5 2 3 6 11 7 7 10 5 3 11 6 15 8 11 5 10 8 8 5 10 12 6 9 11 8 14 12 9 14 8 17 11 12 12 11 12 14 4 9 6 9 4 7 8 9 17 7 17 8 12 7 12 4 7 9 7 7 2 9 10 13 10 5 7 10 7 11 3 8 3 7 7 4 7 6 4 4 4 1 3 5 8 3 3 4 1 4 5 7 4 8 4 12 5 6 6 5 9 2 3 6 5 5 7 4 2 8 5 2 6 8 5 6 6 1 3 5 4 2 5 5 3 4 4 5 1 3 5 4 4 8 3 6 5 8 3 4 4 6 8 8 11 5 5 7 6 5 3 9 7 8 5 4 5 0 4 2 3 2 8 6 3 2 6 6 3 1 7 3 2 2 2 0 1 2 3 2 3 6 2 1 0 4 2 4 4 2 1 3 4 6 4 4 4 0 3 2 1 0 2 2 2 4 1 3 5 7 6 1 1 3 1 3 3 1 2 3 4 2 1 0 0 3 4 2 4 2 4 1 5 2 3 1 4 0 0 0 1 3 3 1 1 2 5 1 6 4 2 0 1 3 1 2 2 3 4 6 8 3 11 2 7 1 6 8 12 4 5 7 5 4 2 7 7 3 2 8 5 7 4 5 5 2 4 6 2 7 2 4 2 9 3 3 6 4 1 1 2 6 1 2 3 0 1 0 5 3 1 2 1 1 2 3 1 3 2 2 4 3 2 4 2 0 3 1 1 3 2 1 1 1 3 0 1 2 1 0 0 2 1 3 0 4 1 1 1 1 0 1 0 1 4 2 1 2 0 6 1 2 2 3 1 3 1 2 1 0 0 0 0 5 1 3 1 2 0 0 1 1 0 4 1 2 1 5 2 1 1 1 1 1 2 2 2 2 0 2 5 3 0 0 1 1 2 0 2 2 2 1 0 1 3 1 2 2 2 5 1 4 2 0 0 0 3 1 2 2 1 0 1 2 2 1 2 0 1 0 1 1 1 1 1 2 3 1 0 3 4 0 2 3 1 7 2 2 1 0 4 2 1 2 0 0 0 1 2 0 1 3 5 2 1 1 1 3 3 0 1 0 3 2 4 2 1 0 1 2 3 3 4 1 1 0 0 0 2 0 1 0 0 2 2 1 5 2 3 3 2 1 0 0 3 4 2 3 1 0 1 0 4 1 0 2 0 0 1 60 93 101 117 116 75 72 83 14 2 2 1 0 0 1 0 0 0 0 0 0 1 2 1 0 1 1 1 1 0 2 2 1 1 0 6 2 2 2 1 4 1 2 4 2 1 0 1 1 1 0 1 2 3 3 3 0 2 2 1 0 1 0 1 0 0 1 3 2 0 0 0 1 1 0 2 1 1 0 2 1 2 1 0 1 0 2 1 1 1 1 2 0 2 0 0 0 0 0 2 0 2 2 0 0 0 0 1 0 0 1 1 3 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 2 2 1 1 1 0 0 1 0 1 0 2 0 2 1 2 1 0 0 2 1 1 0 0 1 1 1 0 0 1 2 0 0 0 1 0 2 1 1 0 0 5 1 1 0 0 2 1 1 0 1 1 2 1 1 1 0 4 4 1 1 1 3 0 0 0 0 2 0 1 3 0 1 0 1 0 3 0 0 1 1 0 0 1 2 2 2 0 1 0 0 1 2 0 2 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 3 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 2 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 3 0 0 3 2 3 0 5 1 1 1 0 1 0 0 2 0 0 1 1 1 2 0 0 1 1 0 0 1 1 0 2 0 2 0 
];
B = [
0 0 0
 20760 6107 14653
 10023 3236 6787
 34186 11076 23110
 22969 6882 16087
 13261 3829 9432
 32841 10245 22596
 26697 7766 18931
 15634 4761 10873
 45656 13717 31939
 45217 12490 32727
 8708 2715 5993
 132114 38951 93163
 18072 5527 12545
 5568 1662 3906
 30101 10496 19605
 10056 3510 6546
 2836 931 1905
 32829 11090 21739
 2743 949 1794
 2562 799 1763
 627 196 431
 18 3 15
 538 152 386
 51169 19067 32102
 2997 953 2044
 3878 1278 2600
 50542 17503 33039
 2631 879 1752
 5331 1806 3525
 79857 26356 53501
 5284 1799 3485
 9249 3113 6136
 54596 18737 35859
 30403 10484 19919
 48749 16329 32420
 102141 34746 67395
 81571 27977 53594
 46934 15759 31175
 119204 41396 77808
 48205 16549 31656
 3347 1143 2204
 119556 42094 77462
 1787 655 1132
 3182 1100 2082
 164833 58333 106500
 3058 1026 2032
 37987 13137 24850
 232372 84538 147834
 36658 12586 24072
 1 0 1
 1556680 582496 974184
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
5 5 0 0
4 1 0 0
2 1 0 0
7 1 0 0
9 5 0 0
25 1 7 0
61 2 21 0
54 6 11 1
74 8 18 11
242 9 20 25
525 6 25 19
1112 6 27 22
2289 23 57 51
5726 17 76 43
13146 33 101 67
30832 62 112 147
62192 139 246 212
80909 347 335 314
66599 596 404 411
37365 758 482 512
13169 872 611 724
2405 1042 669 752
938 1024 868 635
863 1158 956 745
774 1109 915 1088
752 1627 680 996
935 672 568 557
816 588 690 597
756 1228 729 631
745 700 656 736
800 696 685 795
1863 778 811 713
877 867 826 826
925 933 966 911
1059 1023 891 989
1131 1149 1186 1140
1312 1357 1281 1257
1392 1399 1392 1431
1614 1558 1583 1672
1851 1820 1868 1785
2018 2040 2145 2063
2391 2496 2330 2340
2683 2657 2714 2630
3051 3014 3087 3116
3503 3499 3452 3472
3846 4036 4127 4055
4455 4397 4656 4459
4935 5055 5028 5013
5558 5566 5595 5564
6135 6190 6019 6095
6587 6780 6772 6624
7228 7179 7195 7067
7620 7616 7752 7745
8259 8109 8122 8172
8888 8807 9453 8626
9213 9327 9304 9169
9878 9747 10007 9778
11017 10622 10440 10645
11409 11375 11390 11104
12439 11864 11729 11941
12881 12917 12958 12624
12748 12681 12881 12607
12611 12258 12801 12156
11359 11050 10597 11057
8617 9927 9748 7810
4342 5004 4688 4395
2088 3956 2866 2113
1876 2257 2783 1856
1387 1493 1360 1033
1158 930 1785 790
533 550 631 759
631 507 449 482
35 20 11 20
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
