A = [
30823 31303 223892 29773 25674 24480 25019 24819 26177 27912 30225 33441 36596 39968 43205 46746 50593 54888 58938 63163 67591 71955 76250 79349 83145 87796 87590 87111 88081 79224 77928 76100 64476 62814 59018 55735 52860 48767 46337 43533 41032 39761 37673 36750 35769 34384 34104 33380 32953 32570 32565 32111 31777 31699 31109 31598 30644 31084 30931 30518 30414 30261 30305 29840 30268 30150 30349 32027 32631 32278 34095 34184 34687 34569 34139 33933 34035 33835 33926 33728 33314 33213 33012 33057 32672 32795 32241 32182 31958 31611 31764 31320 31528 30868 30750 30603 30468 30199 30164 29540 29356 29017 28777 28170 28145 28260 27779 27666 27655 26930 27056 26537 26304 25897 25717 25620 25455 24742 24695 24328 24428 23853 23653 23588 23342 23155 22648 22339 22456 21827 21751 21373 21122 20686 20812 20536 20180 19839 19822 19484 19027 19149 18521 18310 18072 17776 17536 17137 16866 16984 16623 16231 16173 16119 15743 15504 14933 15028 14825 14754 14455 14219 14109 13895 13679 13545 13418 13139 12913 13057 12696 12497 12365 12396 11885 12001 11716 11481 11357 11031 10866 10698 10544 10292 10184 10169 9867 9799 9527 9386 9144 9172 8788 8800 8557 8472 8228 8096 8066 7870 7704 7634 7575 7361 7295 7015 7131 6989 6882 6790 6589 6384 6317 6221 6241 5992 5816 5895 5903 5710 5671 5561 5482 5288 5316 5178 5103 5063 4942 4792 4765 4759 4513 4529 4390 4481 4360 4273 4080 4110 3923 3994 3962 3840 3686 3703 3521 3624 3396 3435 3467 3330 3247 3255 3182 3141 2986 2952 3109 2996 2877 2846 2863 2853 2790 2705 2679 2611 2706 2730 2540 2604 2497 2595 2743 2520 2335 2235 2376 2198 2153 2154 2126 1998 1978 1930 1762 1922 1832 1844 1808 1734 1737 1725 1684 1633 1660 1676 1560 1530 1473 1494 1485 1453 1399 1393 1316 1363 1268 1349 1233 1290 1213 1183 1226 1187 1150 1157 1114 1087 1099 1126 1123 1048 1001 982 996 943 899 917 933 948 782 880 854 902 835 801 799 788 786 785 724 745 726 742 710 719 702 685 678 666 655 706 660 653 609 635 649 611 602 601 623 525 585 569 519 524 526 538 523 509 471 487 468 482 495 477 461 420 481 466 421 455 422 436 438 411 378 377 389 402 356 402 387 357 343 355 354 372 320 354 326 334 344 323 316 309 296 300 280 309 268 320 310 282 301 276 281 285 269 262 229 268 262 253 254 259 280 288 248 251 256 276 218 200 217 235 247 213 226 212 207 222 215 208 215 210 202 218 205 168 190 195 199 208 207 193 197 174 197 203 181 202 199 169 174 184 166 167 199 186 145 142 182 167 156 174 189 148 166 150 136 122 152 130 152 112 155 158 152 144 161 143 146 151 131 138 157 118 139 140 136 127 140 124 135 128 117 116 128 102 116 125 109 114 121 134 119 109 95 112 122 116 104 110 97 116 90 96 101 105 108 111 107 87 100 86 107 97 95 99 102 109 82 103 115 102 102 99 88 92 96 81 87 84 99 75 86 105 74 95 89 88 99 96 87 80 71 93 72 77 86 87 78 64 73 85 73 66 69 78 97 64 72 97 85 80 64 85 70 83 78 75 76 76 62 87 86 71 72 64 88 84 77 67 79 78 90 67 72 68 60 75 66 65 68 76 55 69 64 75 53 75 68 77 70 64 57 57 70 61 73 64 69 62 59 65 66 53 53 76 60 66 50 47 63 75 62 62 54 64 55 53 54 52 55 49 57 43 47 49 42 53 53 45 56 55 53 61 41 50 43 49 55 47 59 49 40 44 38 60 47 48 48 53 63 45 45 51 50 46 46 37 41 54 47 39 46 41 40 35 43 38 50 46 40 38 29 42 27 38 38 36 35 46 35 36 41 38 33 43 34 36 28 37 38 36 36 35 43 38 28 39 39 39 35 35 37 37 38 32 18 37 30 38 28 26 33 33 45 33 24 30 40 32 33 23 35 33 40 25 35 44 33 29 40 40 24 29 38 41 28 27 30 24 29 38 57 50 79 95 69 93 90 99 115 101 70 96 94 99 109 113 108 84 88 59 83 94 78 84 78 64 68 77 80 61 94 79 63 75 70 48 53 41 28 31 47 27 33 24 22 26 31 25 24 25 29 22 24 20 15 21 28 20 20 26 25 30 29 20 24 20 23 23 19 19 26 31 19 24 28 14 25 20 27 14 26 25 22 15 17 17 25 26 18 21 13 21 20 24 23 21 20 16 18 17 13 32 27 40 34 34 28 29 28 28 35 32 27 32 56 58 48 35 52 52 71 97 53 69 93 157 168 175 173 196 177 225 230 171 165 109 112 86 38 20 26 34 34 31 23 36 36 36 52 42 50 58 40 46 41 23 39 33 36 34 50 29 35 34 20 30 36 29 35 27 36 20 23 24 22 25 15 15 17 18 18 9 16 16 14 15 16 14 6 24 12 12 10 14 8 17 12 20 13 10 6 18 11 14 13 13 10 12 13 15 11 16 11 15 17 5 22 17 6 12 11 10 15 15 20 12 14 12 19 9 20 17 12 18 17 11 18 15 12 7 23 11 15 23 13 27 25 32 33 15 28 33 45 38 34 31 42 35 33 35 31 45 21 20 23 29 24 38 28 25 28 28 34 29 20 29 21 29 24 20 19 15 22 11 19 14 11 12 20 16 17 10 14 15 14 15 14 17 14 13 8 10 12 11 8 3 11 10 9 12 8 8 12 3 6 10 6 12 4 4 7 8 4 11 8 7 8 3 5 5 7 7 6 7 6 5 10 3 8 6 9 7 4 3 6 8 7 2 9 11 7 7 11 5 9 7 6 6 8 12 6 8 8 8 7 5 8 4 8 6 6 6 8 2 6 7 4 3 6 5 4 3 6 4 9 3 9 4 7 6 4 3 6 9 5 4 5 6 11 5 8 6 5 7 5 3 6 6 5 1 7 4 5 2 5 4 6 3 5 3 12 5 6 7 10 6 4 7 7 8 6 4 5 6 6 7 2 5 6 7 6 3 5 3 4 3 6 8 5 6 5 7 2 2 0 4 6 3 5 2 6 8 3 2 3 3 5 2 2 4 2 3 1 2 5 1 4 0 3 2 5 3 2 3 5 1 2 5 1 2 6 3 6 3 1 4 4 1 3 1 1 6 4 4 4 6 2 3 3 3 5 2 5 2 3 0 2 3 1 1 3 3 2 3 1 2 1 2 3 3 3 4 4 3 3 5 4 1 4 1 1 5 4 2 4 3 5 3 7 2 4 6 4 3 4 3 3 2 1 2 2 4 3 0 5 5 0 3 6 3 3 2 2 3 3 5 3 3 3 3 0 3 2 2 1 1 3 2 2 5 3 1 3 2 0 2 0 3 2 3 4 1 4 4 2 4 1 3 0 4 0 5 4 1 3 1 3 2 1 1 1 1 3 0 2 1 1 3 3 0 6 2 3 3 5 3 2 1 0 1 0 0 0 3 0 3 6 3 1 0 3 1 2 1 2 2 2 2 1 2 2 2 0 3 0 2 0 1 3 1 0 0 2 2 2 3 1 2 1 1 2 2 1 2 1 0 2 1 1 1 1 2 7 4 2 1 2 0 3 4 1 1 1 0 3 2 0 0 1 0 1 2 1 3 3 2 1 1 2 2 0 2 4 1 3 0 1 0 0 1 2 3 3 1 3 1 2 3 1 2 2 4 0 2 3 0 0 2 2 1 1 3 1 0 4 2 1 0 0 0 3 1 1 1 2 1 1 2 0 1 1 0 2 1 2 2 1 1 2 5 0 3 1 1 1 1 0 1 0 1 0 1 0 1 1 0 0 1 2 2 1 0 4 1 1 1 1 1 1 1 3 1 0 3 0 1 0 0 3 0 2 1 2 2 0 1 0 1 1 0 2 0 0 3 0 0 0 1 2 1 1 0 1 1 0 3 0 1 0 1 2 2 1 1 0 1 2 1 2 0 1 2 0 0 1 0 0 0 0 2 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 2 0 1 2 1 0 0 0 2 1 0 2 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 3 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 2 0 0 2 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 2 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 2 1 1 0 0 1 0 1 0 0 0 2 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 3 1 0 2 0 0 2 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 2 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 2 0 0 1 1 0 1 
];
B = [
0 0 0
 16754 9411 7343
 18860 10964 7896
 16636 9540 7096
 26836 17684 9152
 19227 13190 6037
 14523 10558 3965
 12224 8775 3449
 8969 6301 2668
 7261 5275 1986
 5215 3866 1349
 5928 4415 1513
 6656 4912 1744
 7049 5229 1820
 16636 12860 3776
 11408 8844 2564
 11572 9161 2411
 10545 8554 1991
 10678 8774 1904
 10513 8571 1942
 9359 7615 1744
 13366 10838 2528
 11874 9632 2242
 10991 8964 2027
 9985 8165 1820
 11430 9318 2112
 10866 8982 1884
 13190 10832 2358
 9885 8153 1732
 12299 10195 2104
 11858 9741 2117
 11385 9352 2033
 12571 10284 2287
 12488 10263 2225
 15831 13034 2797
 12607 10484 2123
 14029 11527 2502
 28231 22707 5524
 13407 11096 2311
 15877 13127 2750
 25724 20856 4868
 16682 13734 2948
 24424 19879 4545
 13715 11450 2265
 17077 14143 2934
 25396 20755 4641
 17134 14203 2931
 25268 20683 4585
 17599 14702 2897
 25578 21023 4555
 17530 14662 2868
 25926 21417 4509
 19641 16336 3305
 25784 21356 4428
 18013 15150 2863
 28204 23399 4805
 25960 21577 4383
 18237 15314 2923
 26737 22322 4415
 16701 14261 2440
 2441263 2165114 276149
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 6 0 0
0 1 0 0
0 0 0 0
1 1 0 0
0 0 0 0
3 1 0 0
4 1 1 0
15 1 0 1
237 4 0 0
3781 2 5 1
17002 7 40 7
59172 5 49 18
157233 7 74 24
282989 11 94 57
336372 29 142 123
293876 47 194 193
194621 74 252 251
101848 115 384 404
41374 165 500 537
11491 259 749 675
2732 346 862 882
1397 549 1090 1155
1542 872 1321 1411
1694 1140 1674 1668
1997 1701 2036 2183
2330 2029 2452 2432
2820 2534 2983 2828
3298 3031 3719 4010
4061 3688 4047 3864
4649 4217 4489 4543
4992 4580 4989 4891
5415 5082 5298 5477
5772 5651 5842 5744
5835 5768 6039 5870
6045 6024 6001 6115
6235 6271 6494 6493
6298 6502 6407 6483
6518 6425 6473 6693
6677 6757 6802 6784
6859 6821 6916 6840
7108 7027 7236 7210
7286 7163 7445 7416
7488 7485 7682 7633
7646 7923 8018 7980
8210 8248 8324 8208
8440 8299 8518 8499
8809 8789 8935 8939
8968 9115 9247 9077
9278 9365 9274 9330
9470 9287 9353 9319
9227 9363 9348 9388
9098 9053 9194 9227
9025 8816 8867 8863
8412 8325 8426 8530
7928 8080 8006 8012
7513 7380 7337 7446
6965 6846 6628 6829
6287 6145 6189 6169
5772 5722 5641 5905
5146 5304 5152 5119
4849 4732 4816 4700
4392 4488 4403 4430
4095 4213 4228 4188
4006 3932 3945 4087
4058 4061 4043 4193
4277 4287 4229 4222
4567 4539 4572 4647
4979 4863 4890 4792
5471 5366 5405 5467
6072 6074 6167 6065
7035 7138 6885 7090
7435 7455 7350 7459
8038 7840 7823 8007
8202 8346 8109 8200
8111 8182 8041 8052
7376 7392 7300 7299
6277 6111 6181 6031
4323 4144 4169 4239
2220 2175 2114 2202
780 779 801 797
111 126 119 137
0 1 2 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

];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 
];
