A = [
37068 37645 245475 35514 31092 29544 30392 30090 31512 32798 35368 38887 41840 44741 48759 53019 57110 62205 67093 71754 76264 81832 86021 90477 94227 99396 100057 99546 101525 91173 91855 89576 76587 74722 70598 67099 64001 59969 56741 54131 51480 49151 47314 45595 44535 43231 43050 42071 41321 40847 40389 39723 39396 39190 38708 38608 38389 38260 37810 37608 37474 37176 37463 36924 36831 36828 36801 39205 39220 39175 41617 41874 41948 41505 41362 40811 41524 41050 40835 40560 40592 39733 39488 39270 39419 39050 38841 38959 38462 37944 38106 37287 37285 36852 36895 36237 36056 35812 35336 35033 35190 34545 34270 33688 33616 33365 33159 32431 32241 32236 31814 31589 31267 30817 30335 30126 29816 29399 28972 28893 28742 28251 27974 27686 27456 26956 26527 26265 26270 25798 25410 25284 24950 24334 24190 23723 23592 23401 23035 22780 22157 21948 21759 21425 21122 20803 20431 20218 20032 19736 19501 19213 19005 18766 18097 17975 17714 17610 17250 17142 16836 16328 16478 16230 16214 15741 15737 15283 15351 15011 14973 14448 14393 14135 13972 13675 13733 13295 13288 12683 12400 12424 12019 12172 11957 11479 11481 11262 10897 10919 10768 10484 10285 9858 9912 9686 9675 9454 9325 9248 8888 8749 8670 8709 8485 8231 7978 8052 7996 7742 7580 7578 7451 7264 7089 6987 6928 6939 6821 6537 6531 6325 6174 6367 6214 5962 5944 5823 5802 5626 5566 5504 5427 5361 5064 5173 4909 5067 4827 4841 4744 4761 4587 4583 4467 4310 4131 4211 4068 4221 4013 4013 3909 3839 3727 3715 3679 3644 3625 3574 3471 3402 3360 3312 3298 3237 3215 3225 3177 3164 2935 2969 3144 3077 3041 3069 2784 2813 2665 2522 2634 2490 2495 2361 2315 2371 2233 2244 2219 2093 2045 2038 1998 2088 1987 2028 1920 1851 1865 1806 1802 1741 1697 1771 1700 1625 1594 1688 1517 1601 1590 1523 1506 1515 1460 1420 1332 1406 1363 1345 1343 1237 1276 1181 1261 1195 1214 1154 1171 1178 1161 1125 1041 1109 1040 1135 1043 1058 1010 997 947 929 975 941 925 950 870 880 879 904 852 798 860 796 840 755 813 755 816 713 750 747 785 745 695 686 685 697 686 675 658 632 626 654 629 613 636 592 579 569 560 514 526 529 541 510 467 510 515 496 491 510 488 498 501 480 484 479 467 448 463 431 485 441 444 393 394 392 395 330 385 390 384 391 386 345 356 351 362 363 360 319 330 355 308 329 311 318 376 351 330 333 309 274 290 295 286 286 295 250 273 274 274 272 275 269 249 264 269 288 265 254 246 216 235 232 255 226 223 215 215 230 254 236 232 236 226 249 199 181 210 206 207 216 225 200 221 212 200 195 191 193 195 181 207 186 200 178 160 178 167 177 201 175 166 181 185 160 178 182 166 161 178 151 148 160 151 146 149 156 164 154 153 151 155 135 153 128 143 134 125 146 141 112 145 145 136 139 131 132 130 148 111 140 122 124 103 114 120 106 124 101 147 96 97 109 112 110 117 105 116 109 108 100 144 113 121 115 105 126 99 111 105 122 126 94 104 97 105 105 112 98 93 82 77 91 126 79 91 91 89 88 98 108 83 100 83 98 88 79 83 93 98 87 85 91 88 89 80 93 94 95 98 85 92 77 85 77 84 76 96 76 96 84 83 88 97 87 82 89 70 75 64 77 67 80 67 77 67 79 67 86 63 54 73 71 79 72 63 72 58 57 58 71 78 67 82 71 83 67 74 71 73 63 80 62 83 66 52 48 66 62 57 54 52 58 58 45 68 63 53 57 55 66 65 43 76 72 56 49 63 57 62 58 44 65 45 51 42 56 50 60 48 59 34 59 56 49 54 52 53 53 41 52 48 64 48 51 48 59 47 60 44 51 45 43 44 47 33 50 56 56 38 46 48 45 47 36 54 37 38 37 53 57 37 39 45 32 51 58 42 40 39 37 42 42 34 32 46 45 41 43 38 43 44 35 38 42 37 46 40 31 52 40 47 34 30 33 37 42 35 43 44 43 44 42 46 36 53 60 61 94 76 80 104 95 92 102 103 92 119 94 106 121 112 98 109 63 85 82 79 77 81 80 73 76 88 79 95 87 71 81 80 52 41 45 36 34 36 38 44 45 44 32 29 31 27 26 30 28 28 37 25 33 34 37 29 22 27 34 36 24 40 24 28 28 26 28 31 27 26 32 18 25 26 24 26 25 36 29 22 28 25 18 30 16 31 20 21 26 22 35 20 27 38 23 27 22 29 33 31 30 26 22 24 32 30 31 26 31 23 42 40 72 58 42 40 64 85 106 64 79 116 126 170 171 214 230 202 249 247 228 195 105 134 100 52 29 32 33 31 31 37 36 36 57 49 38 52 51 48 39 34 35 34 30 35 29 48 32 32 39 25 34 36 21 47 30 36 21 21 21 25 22 22 22 19 21 15 24 20 13 14 14 8 18 17 22 19 12 11 13 18 17 17 13 18 13 17 18 5 13 17 8 26 18 16 20 24 19 18 22 15 16 24 10 16 15 17 16 19 15 18 18 15 25 18 27 18 18 24 17 10 21 11 14 15 18 17 16 19 14 23 23 26 28 25 35 36 47 53 47 38 43 45 33 49 30 38 46 28 33 31 20 29 28 36 36 23 28 30 22 26 26 17 21 27 18 25 22 18 14 13 21 15 17 21 20 16 15 7 13 8 15 16 15 18 17 13 11 13 6 7 10 8 10 13 10 10 8 10 10 10 4 12 8 17 6 7 7 5 9 9 8 3 4 8 3 10 11 11 4 4 13 7 11 4 9 11 7 7 12 7 5 14 10 9 7 15 2 8 3 8 7 5 6 8 6 9 5 8 1 6 8 13 6 6 6 10 6 8 6 2 6 6 7 9 4 8 8 9 3 9 3 8 8 6 4 10 6 5 5 10 2 7 3 4 4 10 2 8 5 8 5 7 4 7 7 2 8 3 0 14 4 7 4 8 7 8 6 3 10 4 6 8 9 9 6 3 2 9 4 4 6 5 6 5 3 7 3 6 7 7 6 3 3 8 7 6 5 2 4 4 6 6 5 7 7 2 1 6 3 6 2 2 4 4 3 5 5 1 6 2 3 5 1 5 4 7 2 3 8 4 6 3 7 3 1 5 2 5 7 4 4 3 5 1 6 5 3 2 5 4 2 7 4 2 1 4 5 5 4 3 7 5 5 4 8 2 2 5 5 6 5 4 7 7 3 2 6 3 0 2 3 2 5 5 5 3 2 3 2 2 0 4 3 4 3 3 1 5 3 4 3 4 3 5 4 3 3 3 1 1 1 4 2 4 2 0 3 1 2 2 5 4 2 2 6 3 5 1 5 4 2 3 2 4 1 2 2 4 4 4 3 3 0 1 1 5 5 3 7 3 5 5 3 2 5 3 1 4 4 3 0 3 2 1 6 1 5 1 1 4 1 2 2 1 4 2 3 1 1 3 2 7 4 5 2 2 4 1 3 3 1 2 4 1 1 3 4 1 0 0 3 2 1 3 1 1 1 1 4 4 1 2 1 3 2 1 1 1 3 0 1 0 4 3 3 1 4 2 2 3 1 2 0 3 1 3 1 2 2 4 1 2 1 2 1 0 2 3 1 2 4 2 2 0 5 0 2 4 1 2 4 3 1 1 0 3 2 2 1 3 4 0 1 3 0 1 2 0 2 1 3 1 3 0 1 3 3 2 1 1 1 2 1 1 4 1 1 2 0 0 4 2 1 1 5 4 1 0 1 0 1 3 1 1 1 1 2 1 2 3 2 2 3 3 5 0 3 2 2 1 0 1 1 2 1 2 0 1 1 2 3 1 1 1 2 0 1 0 1 0 2 1 2 1 2 1 2 0 0 2 2 1 1 1 0 1 1 3 1 1 1 0 1 1 0 2 0 0 1 1 0 3 4 1 1 1 0 3 1 2 4 3 0 1 1 2 1 3 3 2 2 2 2 0 2 0 1 2 1 1 1 0 0 0 2 1 2 2 3 0 1 2 0 1 1 0 1 1 0 0 0 0 0 1 2 0 0 1 0 0 0 0 1 1 0 2 2 2 1 2 0 1 2 0 0 0 0 1 0 2 0 0 1 0 0 1 1 0 5 0 0 0 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 2 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 2 0 2 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 2 0 1 0 0 0 1 0 2 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 2 0 0 0 1 2 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 2 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 2 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 2 0 0 1 0 0 1 0 0 0 0 0 0 2 0 1 0 1 
];
B = [
0 0 0
 19165 10772 8393
 21633 12401 9232
 18783 10578 8205
 30829 20130 10699
 21982 14871 7111
 16433 11527 4906
 14066 10019 4047
 10710 7658 3052
 8715 6293 2422
 6068 4450 1618
 6999 5165 1834
 7805 5686 2119
 8328 6083 2245
 19308 14735 4573
 13228 10124 3104
 13420 10360 3060
 12173 9697 2476
 12117 9812 2305
 12196 9799 2397
 10865 8693 2172
 15540 12458 3082
 13352 10716 2636
 12747 10205 2542
 11713 9433 2280
 12958 10536 2422
 12502 10207 2295
 15636 12709 2927
 11691 9599 2092
 14340 11639 2701
 14149 11564 2585
 13549 10983 2566
 14976 12257 2719
 14903 12121 2782
 18724 15186 3538
 14474 11823 2651
 16599 13589 3010
 33586 26724 6862
 15692 12716 2976
 18660 15125 3535
 30837 24799 6038
 19517 15921 3596
 29579 23832 5747
 16324 13436 2888
 20255 16547 3708
 30490 24641 5849
 20200 16606 3594
 30368 24701 5667
 21107 17398 3709
 30829 25129 5700
 20270 16745 3525
 30565 25009 5556
 23802 19560 4242
 31349 25637 5712
 21783 18039 3744
 33541 27425 6116
 31453 25862 5591
 21945 18257 3688
 32193 26488 5705
 19803 16798 3005
 2878697 2530099 348598
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1 1 3 1
1 0 0 0
0 0 0 0
1 2 0 0
1 2 0 0
0 4 0 0
6 3 0 0
25 3 2 3
322 1 2 1
4525 2 12 1
20177 2 62 11
67002 6 92 19
175666 8 93 49
316921 17 111 75
376532 16 172 158
329220 38 248 230
219324 75 341 330
117988 129 510 516
51158 206 683 695
16500 345 948 896
4512 488 1142 1190
1988 682 1423 1488
1917 1008 1757 1812
2188 1425 2248 2089
2492 1939 2691 2651
3004 2516 3076 3217
3642 3163 3763 3654
4162 3844 4593 4887
4853 4686 4922 4913
5479 5191 5615 5697
6070 6005 6217 6157
6740 6275 6654 6608
7129 6977 6991 7034
7316 7163 7357 7415
7500 7424 7588 7631
7634 7609 7819 7598
7626 7952 7922 7991
7974 7917 7907 8091
8136 8068 8232 8362
8326 8179 8437 8434
8433 8547 8531 8701
8661 8744 9096 8800
9130 9072 9183 9286
9614 9653 9460 9548
9827 9931 9956 9938
10251 10470 10338 10259
10576 10773 10741 10927
11168 11114 10907 11018
11299 11339 11276 11355
11217 11192 11499 11220
11060 11242 11209 11244
11031 11126 10905 11128
10644 10690 10576 10504
10118 10024 10074 10100
9506 9474 9606 9637
8694 8912 8816 8965
8053 8096 8046 8202
7528 7280 7367 7480
6693 6684 6588 6734
6074 6131 6111 6086
5594 5690 5730 5552
5273 5290 5228 5340
5091 4962 4987 5034
4666 4852 4836 4880
4753 4799 4803 4915
5024 5058 4953 4954
5271 5315 5390 5420
5776 5815 5869 5769
6410 6633 6574 6499
7438 7365 7138 7261
8264 8449 8200 8308
8998 8880 8935 8866
9500 9458 9436 9516
9775 9756 9720 9780
9578 9790 9615 9788
8723 8743 8959 8720
7328 7429 7359 7265
5123 5078 5140 5034
2699 2640 2628 2665
961 977 1032 991
149 140 159 150
2 2 0 3
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
