A = [
102980 94646 155601 100848 94692 89895 87678 88307 99325 98611 117920 113478 124829 153054 185982 228834 250483 254631 253684 256521 228006 195697 177109 171215 171283 197536 197984 197043 206780 172467 174581 160183 124778 126986 123371 127098 126895 114563 117428 114723 109656 115059 112832 116039 122375 121755 117543 115384 120194 115671 109311 110075 114113 114226 115013 118472 112806 116318 116321 107778 105540 107144 107456 106339 109303 113598 112187 111063 109893 109312 106038 105379 107801 107145 110206 111919 113491 110662 109392 106905 103190 104119 100383 99871 101662 101549 99350 97459 96937 95524 94314 93818 92909 92138 91848 93224 91335 92383 92392 89658 88443 88292 86735 85310 86975 87080 86547 87445 86104 85852 84265 83558 82629 82194 82463 82039 82849 83100 82914 82176 82020 80164 79639 78535 78830 78824 78686 78700 78523 78009 77650 77127 75645 75520 74700 74544 74524 74322 73962 72844 74284 72853 72252 71544 70339 70685 71095 70498 70858 71309 70906 69431 69136 67858 67952 67040 66483 66217 65698 65712 65517 65102 64295 63809 63166 62904 62965 63189 62649 62865 62159 61145 61390 61733 60541 60049 59998 59334 58930 58935 59520 58650 58486 58074 57732 57046 57386 56588 57164 56866 56129 55857 55534 55485 54929 54798 54879 54042 54332 53868 53492 53031 53212 52723 52561 52198 51996 51675 50945 50783 50805 49906 49218 49338 49095 48308 47542 47134 47325 46949 47262 46556 46421 46691 46282 45765 44899 45191 44983 44409 43680 43907 43556 43179 42305 42436 41956 41445 41439 40484 40666 40651 40550 39926 40005 39662 39213 38992 38887 38386 37788 37700 38184 37134 37129 36890 36634 36648 36045 36147 35507 35497 35306 35091 34867 34236 33957 34165 33883 33803 33107 32854 32826 32894 32521 32228 32394 32133 31848 30968 31157 31194 30756 30294 30293 30331 30089 29425 29684 29705 29251 29262 28896 28618 28562 28392 28098 27767 27382 27326 27384 26886 26860 26333 25925 25727 26282 25670 25280 25177 24983 24743 24413 24014 24221 23663 23160 23433 23166 23090 22668 22823 22362 22119 21999 21713 21448 21252 20841 20619 20836 20685 20177 19884 19704 19306 19352 18999 19457 18711 18370 18097 18061 17357 17437 17034 17292 16758 16646 16354 16344 15914 15861 15485 15191 15168 14899 14552 14501 14493 13765 13906 13265 13068 13100 12886 12401 12255 11959 11984 11561 11344 11345 10872 10742 10519 10275 10019 9715 9534 9352 9269 8920 8892 8844 8549 8356 8041 7814 8020 7510 7471 7403 7295 6799 6483 6545 6181 5975 6015 5988 5623 5581 5302 5267 5260 5176 4890 4707 4637 4443 4342 4216 3968 3958 3775 3708 3557 3477 3278 3411 3222 2984 3071 2908 2700 2680 2658 2554 2396 2459 2376 2228 2230 2131 2052 2010 1972 1856 1862 1806 1632 1637 1647 1561 1546 1465 1432 1303 1345 1211 1150 1216 1174 1127 1105 972 984 905 968 911 877 864 844 794 748 777 719 725 725 637 614 616 566 544 546 557 516 543 502 493 443 456 464 426 415 397 358 406 345 364 379 358 341 304 345 335 361 266 299 267 276 283 221 266 204 243 235 211 166 173 177 155 169 153 144 160 130 143 136 128 136 130 139 120 131 112 102 101 92 81 99 102 92 84 96 89 70 83 69 84 70 81 80 73 74 76 84 67 65 56 69 61 79 54 77 68 60 51 69 54 75 64 59 59 106 185 70 104 110 83 58 46 68 59 51 49 61 139 67 71 76 30 80 57 44 42 43 168 88 46 87 84 46 48 61 33 39 47 39 94 26 35 78 124 31 46 57 37 41 44 71 39 34 67 128 42 43 57 29 42 33 22 44 37 28 27 31 42 31 29 30 36 64 48 27 38 138 25 30 48 45 38 37 27 35 23 24 28 31 26 39 22 29 22 35 31 32 25 30 33 21 26 29 24 22 38 28 19 27 24 31 35 27 29 27 34 23 28 28 29 26 36 31 25 17 23 25 34 25 27 22 25 18 19 28 17 29 21 26 19 16 25 26 22 30 15 25 29 23 29 25 25 25 21 19 24 21 13 23 30 17 25 18 30 18 13 17 14 8 20 20 33 32 31 120 64 30 29 46 19 46 60 29 21 28 168 27 22 28 26 55 72 27 33 24 19 41 24 28 23 26 15 24 19 21 11 25 18 25 17 10 18 29 76 39 18 21 16 16 25 19 18 21 26 15 22 14 22 16 15 26 27 28 23 92 26 24 24 25 95 34 16 19 19 29 22 19 24 37 70 50 29 20 32 26 36 18 21 15 17 15 14 11 15 6 23 21 9 13 23 16 15 10 24 14 19 12 17 13 9 15 16 13 16 9 14 20 22 11 19 14 16 19 15 36 14 13 16 97 18 11 33 34 14 25 21 20 21 13 87 14 17 15 11 37 11 15 8 7 13 16 9 16 24 62 21 16 21 25 15 19 12 10 19 14 20 21 20 51 23 23 19 22 55 14 32 33 57 34 15 30 24 18 26 23 17 15 32 33 15 42 13 15 63 35 14 10 19 45 16 13 22 11 59 31 16 18 28 47 31 7 18 15 61 10 4 36 18 27 31 18 22 6 34 35 27 38 35 30 33 17 8 12 32 32 8 8 19 19 23 10 24 6 30 10 17 6 10 29 39 8 14 13 18 22 12 15 7 14 34 14 16 10 30 29 16 20 13 56 38 18 19 16 44 43 14 11 25 36 24 19 35 20 43 35 14 26 12 68 39 8 21 26 18 16 9 9 5 15 12 3 5 8 4 14 10 11 6 21 6 6 2 6 6 9 8 3 5 5 7 21 9 7 4 6 12 12 4 6 11 11 3 5 5 12 10 4 7 2 5 4 4 6 3 6 8 5 11 3 6 6 8 5 8 6 9 3 5 3 3 9 3 2 4 3 7 5 7 6 4 5 6 7 6 13 9 8 14 25 25 22 33 7 42 22 14 17 6 48 30 9 15 5 75 13 13 16 24 31 11 22 31 28 41 40 18 14 16 30 55 18 46 39 66 24 29 5 7 21 16 10 19 3 7 6 8 7 6 9 10 5 4 1 11 2 2 13 8 2 4 11 6 3 2 8 2 1 4 5 5 5 6 6 8 13 5 5 3 7 9 4 0 5 4 4 4 1 0 0 6 6 3 5 10 7 5 2 5 4 3 5 11 6 2 8 3 7 3 4 7 4 5 3 3 0 5 4 1 2 2 6 5 0 3 7 4 7 8 8 5 6 8 3 9 7 5 4 4 32 13 8 7 17 6 4 6 3 19 14 11 12 8 8 16 7 12 13 17 32 15 21 12 10 10 5 14 20 6 13 6 5 4 18 7 2 16 14 16 10 5 13 13 15 15 2 11 16 12 7 6 11 9 2 13 2 8 7 4 16 5 8 4 11 8 2 15 9 13 7 7 4 9 3 5 8 5 4 4 6 6 4 4 3 2 4 8 4 3 2 1 1 3 1 3 6 3 5 0 5 4 1 0 2 3 1 1 3 2 0 2 2 2 3 2 1 1 2 1 2 3 3 0 0 3 3 1 0 4 0 5 2 1 3 0 4 3 4 1 1 1 1 0 3 4 0 0 1 2 5 2 3 0 2 0 1 1 0 1 0 2 2 0 1 2 1 3 2 4 3 6 2 5 1 2 4 5 7 5 0 6 7 2 6 3 2 0 3 4 2 10 1 3 1 4 13 2 6 8 9 3 4 7 4 6 6 4 1 5 0 4 10 4 3 8 2 2 2 3 4 2 5 10 12 2 3 4 4 4 2 2 5 4 11 7 2 5 2 1 1 4 1 4 19 12 2 9 16 12 13 9 6 1 17 1 7 5 1 16 7 5 6 13 25 11 6 0 2 22 1 6 4 4 14 9 7 14 38 25 32 17 3 3 4 20 13 4 2 3 2 4 2 5 16 5 37 2 4 7 41 31 15 6 9 4 8 4 5 4 43 11 7 2 4 7 30 1 3 2 2 8 2 3 5 19 6 4 6 15 12 18 1 5 3 1 13 0 9 8 60 15 7 10 4 6 6 6 4 6 8 31 5 4 8 64 12 8 12 10 69 25 21 4 5 23 33 1 8 4 75 18 5 6 2 2 12 5 2 3 6 31 3 6 3 2 0 2 1 2 2 4 3 1 0 0 1 1 0 3 1 4 3 1 5 0 2 7 5 1 5 1 5 6 4 4 7 5 6 8 8 3 2 11 2 4 2 5 7 2 2 4 4 7 2 4 2 1 5 4 2 2 1 4 0 0 1 5 1 1 2 1 1 2 4 4 14 3 2 5 1 29 1 1 3 3 5 3 2 4 4 3 0 3 2 3 2 9 2 1 0 1 0 2 0 1 1 0 1 0 0 0 1 1 2 0 0 1 2 1 0 0 2 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 0 1 1 2 2 1 2 0 3 2 3 1 1 0 0 0 0 1 0 2 3 0 0 1 0 0 1 1 2 3 1 0 1 1 4 1 2 1 0 0 0 0 0 2 3 0 0 0 0 0 1 0 0 2 1 2 0 3 0 3 0 0 0 0 0 0 1 0 0 2 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 2 0 0 3 3 2 1 1 1 1 0 1 0 0 0 0 1 0 0 3 1 0 2 1 1 0 1 1 1 0 0 2 2 2 0 0 2 0 0 0 0 1 0 0 2 8 1 1 1 1 1 1 1 1 2 2 2 1 1 1 1 3 1 0 0 0 0 0 0 0 2 1 0 0 1 1 1 0 1 0 0 0 0 0 2 1 1 1 2 1 0 0 0 1 1 1 0 0 0 0 1 1 2 0 0 0 0 1 0 0 0 0 1 2 0 0 4 0 3 3 1 1 0 0 2 2 1 0 2 2 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 
];
B = [
0 0 0
 52398 39955 12443
 79009 63871 15138
 56505 45021 11484
 158396 129666 28730
 76678 63246 13432
 52203 44104 8099
 51206 43177 8029
 32678 27210 5468
 27619 23192 4427
 14224 12027 2197
 26004 21946 4058
 21784 18328 3456
 26923 22819 4104
 112227 96353 15874
 42617 36607 6010
 48304 42056 6248
 44649 39184 5465
 37878 33223 4655
 48811 42645 6166
 42195 36800 5395
 91886 79967 11919
 50620 44132 6488
 59376 51669 7707
 50277 44113 6164
 46011 40486 5525
 56346 49494 6852
 67843 59633 8210
 38202 33708 4494
 79144 69242 9902
 63539 55821 7718
 51244 45082 6162
 52110 46167 5943
 61326 53925 7401
 69185 61038 8147
 42956 38125 4831
 73555 64838 8717
 95375 83865 11510
 49033 43506 5527
 59656 52847 6809
 88861 78221 10640
 70308 62165 8143
 71569 63168 8401
 58220 51292 6928
 67337 59691 7646
 73706 65129 8577
 58014 51366 6648
 86287 76108 10179
 67976 60177 7799
 72881 64645 8236
 61728 54680 7048
 86242 76242 10000
 56155 49813 6342
 89828 79389 10439
 54773 48464 6309
 81774 72184 9590
 85933 75845 10088
 52425 46393 6032
 83513 73725 9788
 45665 40668 4997
 9108410 8199571 908839
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 4 0 0
0 0 0 0
0 0 0 0
1 4 0 0
2 1 0 0
5 0 0 0
4 6 0 0
5 5 0 0
11 4 1 2
41 13 8 1
101 17 23 10
222 15 56 50
352 33 111 88
581 75 223 167
1328 121 352 323
6421 299 578 640
78332 465 1085 1049
762035 796 1829 1797
1483127 1679 3220 3368
346551 2963 5122 5064
19753 3761 7174 7070
10293 5375 9172 8988
12112 7762 10874 11230
13725 10417 13085 12967
15549 14011 15522 15652
18998 16562 17962 18345
21526 20255 20751 21401
24981 26336 24299 23811
27671 27598 26636 27069
30309 30408 29601 29816
33444 32168 32322 32530
35740 34792 34783 34971
37090 36978 36544 36943
39476 38527 37977 39014
41347 40823 39812 40734
43492 40897 41528 40710
44710 42515 43711 43536
42347 42782 42282 42780
43810 43332 43346 43695
45061 44762 44608 44681
45474 45931 45990 46083
47173 47167 47282 47161
49062 49419 48734 49036
51145 50907 50986 50506
52992 53595 53179 52873
55050 55436 55569 55772
57787 57506 57476 57610
59185 59496 59340 60048
60780 60746 60754 60649
61472 61819 61750 61163
61423 61513 61379 61236
60086 60203 59752 60209
58323 58080 57377 57815
55471 55461 55353 55463
51996 51873 51880 51913
48328 48089 48031 48258
43823 43951 44149 43967
39926 40273 39744 40079
36147 36444 36275 36298
32872 33178 33059 33197
30988 30570 31092 30920
29339 29313 29208 29079
27821 27908 28010 27623
27778 27762 27631 27707
27972 28065 27951 28397
29383 29260 28844 29424
30951 30828 30630 30872
45590 46383 37065 38778
35516 35414 35951 35747
37097 37691 36990 37187
38515 38392 38618 38404
38165 38496 38151 38272
35609 36111 36247 36141
31117 31023 30871 31050
25700 25930 25602 25673
20315 20459 20332 20397
15083 15132 15072 15262
10317 10185 10482 10291
7395 7583 7312 7562
5189 5242 5146 5221
3443 3479 3451 3328
2309 2327 2342 2327
243 253 262 251
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
