A = [
10664 10770 58834 11273 11175 10899 10967 11065 11220 11253 11632 13084 14873 16925 19583 21774 22773 23504 23984 23528 22914 22701 22464 22474 22403 25750 25768 25392 28033 23838 23569 23361 19120 19498 19053 19338 18809 18267 18176 18027 18459 18301 18274 18441 17932 18344 18051 17984 17882 17664 17792 17773 17617 18020 18015 17903 17844 17485 17518 17059 17397 17425 17420 17394 17336 17301 17527 17074 17390 17203 17169 17067 17015 16891 16828 16714 16657 16858 16673 16546 16190 15839 15874 15890 16100 15941 15826 15656 15327 15400 15488 14881 15221 15176 15479 15024 15108 15100 15044 15211 14915 15069 15138 14774 15066 14867 14955 14797 14602 14479 14277 14242 14285 14456 14075 13741 14145 14062 13945 14155 13798 13801 13605 13612 13788 13423 13181 13453 13504 13207 13310 12913 12640 12561 12204 12339 12365 12294 12385 12326 11963 12112 11766 11717 11960 11946 11885 11790 11947 11750 11640 11550 11060 11122 11268 10975 11032 10807 10727 10834 10708 10580 10582 10683 10498 10446 10297 10323 10367 10669 10368 10324 10378 10015 10148 9838 9814 10203 10052 9882 9886 10396 9776 10095 9704 9578 10235 10282 10291 10519 10398 10585 10274 9859 8675 8532 8735 8614 8328 8061 8208 7866 7792 7646 7524 7626 7474 7460 7440 7163 7146 7130 7070 6893 6930 6864 6770 6653 6604 6590 6466 6475 6522 6485 6360 6244 6373 6312 6211 6391 6139 6332 5896 5989 5989 5929 5753 5658 5656 5775 5421 5380 5447 5364 5140 5166 5227 5225 5128 4955 5080 4908 4889 4837 4648 4760 4870 4722 4834 4868 4532 4570 4741 4898 4583 4556 4279 4431 4305 4390 4437 4172 4192 4227 4069 4065 3811 3889 3711 3580 3861 3518 3584 3625 3356 3364 3425 3569 3368 3250 3386 3272 3128 3395 3200 3313 2987 3230 2943 3004 3022 2779 2768 2938 2652 2898 2518 2593 2625 2485 2513 2435 2456 2473 2198 2249 2111 2159 2080 2006 2068 1978 1951 1900 1960 2628 2159 2017 2086 2008 1848 2112 1686 1676 1622 1565 1581 1541 1469 1479 1370 1317 1409 1318 1404 1304 1295 1318 1161 1264 1199 1257 1208 1151 1128 1127 1115 1100 1045 1069 1072 1032 1020 1089 1065 1077 994 1014 902 1038 924 944 943 938 920 927 940 1004 896 804 773 846 896 832 978 864 915 839 832 959 871 901 1011 840 1063 941 1082 1214 851 971 937 965 705 675 661 546 605 555 525 506 544 577 499 475 460 481 455 468 474 440 474 438 459 387 392 450 420 406 362 354 418 330 335 309 336 346 301 303 321 298 324 292 339 287 316 254 339 284 256 277 260 263 251 267 254 258 267 239 273 239 265 273 279 271 254 266 236 242 283 228 223 248 252 242 254 173 198 204 214 248 226 232 222 189 210 174 190 194 175 169 153 168 151 167 161 147 134 146 155 148 156 159 140 189 149 141 151 138 148 134 140 126 136 148 130 128 139 140 134 141 150 147 133 146 143 134 186 130 110 139 115 114 104 121 119 114 102 113 110 121 87 97 88 86 89 98 104 107 97 86 91 93 93 99 78 93 78 77 101 82 92 72 94 65 82 74 79 74 80 87 92 55 86 73 88 79 77 86 78 70 78 70 80 90 64 71 58 69 67 67 72 65 66 87 76 76 71 76 77 78 64 85 79 82 75 64 74 95 60 70 56 65 68 61 58 65 66 59 59 76 65 67 63 73 55 52 56 52 70 58 73 65 67 45 55 62 50 61 55 44 52 47 51 59 63 55 64 78 71 57 72 72 77 64 61 65 66 70 67 75 65 55 55 48 47 49 64 41 54 58 54 72 62 61 69 75 49 44 60 76 53 63 39 51 42 50 43 51 53 57 56 41 40 38 35 41 39 36 51 34 32 42 41 33 32 35 34 37 33 34 32 48 41 37 40 34 38 36 40 28 41 26 38 40 39 45 44 42 51 34 44 38 40 44 34 28 35 29 37 35 27 41 37 33 27 40 31 28 29 30 32 30 35 37 30 25 30 30 35 36 42 28 33 33 32 37 40 31 26 47 35 42 39 32 38 34 41 32 34 30 44 47 36 53 30 54 35 57 45 57 83 73 84 57 55 64 75 74 80 66 76 89 78 109 139 105 145 105 200 798 460 877 608 480 731 417 581 26 28 14 19 24 28 39 55 92 34 21 33 38 27 34 43 49 62 52 48 44 33 49 46 51 22 26 27 33 27 23 22 25 29 22 24 20 16 18 28 38 23 36 36 39 27 41 27 40 24 29 31 27 36 24 24 16 27 32 28 39 31 309 183 404 277 336 281 415 266 35 27 29 22 41 35 56 56 50 36 40 38 54 50 43 46 65 62 58 46 44 37 47 42 44 41 34 35 45 78 57 47 70 61 61 49 43 57 53 62 61 107 83 111 167 114 140 118 184 133 63 55 59 122 57 47 45 62 85 50 43 30 46 57 45 50 61 58 78 66 57 64 48 44 62 47 50 49 39 48 40 54 53 47 41 43 51 37 57 36 56 27 33 54 44 24 45 40 39 33 47 37 38 34 64 32 44 37 57 35 32 45 47 40 44 39 49 48 50 48 53 52 44 33 38 45 54 52 51 49 43 41 67 29 57 62 61 67 82 100 100 85 82 116 103 131 119 118 100 141 119 99 78 80 92 107 117 136 166 132 131 121 101 114 155 144 132 118 129 123 106 64 73 106 80 66 55 63 50 45 51 38 39 27 42 64 50 23 29 29 26 13 22 13 10 18 15 18 18 13 6 5 9 12 12 7 7 5 9 13 9 5 6 7 9 10 9 10 4 10 10 11 4 17 7 7 16 14 18 7 7 23 20 28 29 25 37 33 34 21 18 21 21 20 26 28 40 28 18 32 24 38 19 20 28 12 17 7 5 6 7 5 6 4 3 10 8 5 3 8 5 4 5 7 5 8 3 8 3 7 9 7 3 2 5 3 6 5 4 5 4 4 3 2 7 11 5 4 5 5 5 6 11 31 39 10 15 9 18 9 8 12 3 10 7 5 5 4 1 2 11 4 2 5 4 5 5 4 6 3 7 6 4 7 8 1 6 6 4 1 0 3 3 3 5 7 5 2 3 3 5 4 1 3 4 7 5 7 6 8 10 12 10 9 24 5 12 10 9 6 4 8 3 8 5 7 3 4 2 6 10 6 7 4 7 7 4 4 6 5 3 5 5 4 1 4 3 3 3 4 2 4 1 2 7 4 1 3 4 4 7 3 2 8 1 3 2 2 1 3 2 6 1 3 4 6 5 5 3 5 1 2 4 4 8 0 1 2 3 2 5 1 2 3 2 2 1 1 1 5 0 2 6 3 0 1 5 0 0 0 3 2 1 4 1 3 4 2 2 1 0 1 2 3 2 1 1 3 1 0 1 3 2 2 2 1 1 2 5 3 2 4 6 0 1 4 1 4 1 2 1 3 1 2 6 2 2 1 3 1 1 5 1 5 5 0 1 0 2 3 4 2 2 1 1 1 1 1 1 3 1 0 2 3 1 0 0 2 1 3 2 2 0 2 2 1 1 2 4 3 1 0 1 5 2 0 2 1 0 2 2 2 1 1 3 0 0 1 3 2 2 1 2 3 2 1 1 2 1 1 2 1 0 2 2 1 2 2 4 3 4 1 3 0 1 3 2 2 3 3 2 4 1 3 0 2 0 2 1 1 5 0 2 1 2 2 2 3 0 1 2 2 2 0 1 0 0 2 1 1 0 4 3 1 1 0 0 2 2 0 0 1 3 1 0 1 2 1 0 0 1 1 1 2 1 0 0 2 1 0 1 2 0 0 2 0 0 1 0 0 1 1 1 1 3 4 0 2 0 2 0 0 1 2 1 0 3 1 0 4 1 1 1 0 1 3 3 0 0 0 1 1 1 0 2 1 0 0 2 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 2 1 0 0 1 0 0 0 1 2 0 0 1 2 1 1 0 0 1 1 1 0 2 1 1 0 0 1 0 3 3 1 2 0 1 0 1 0 2 0 0 0 0 1 1 0 2 0 0 1 1 1 1 1 0 0 4 0 0 2 0 0 1 1 0 0 0 0 0 1 0 1 2 0 2 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 4 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 2 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 2 0 2 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 1 0 0 0 0 0 2 1 1 1 1 1 1 0 0 0 0 0 1 0 0 3 0 1 0 0 0 0 1 1 0 0 2 0 0 0 0 2 1 0 1 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 1 2 0 2 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 2 2 0 1 1 0 0 2 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 2 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 
];
B = [
0 0 0
 27268 9783 17485
 17957 6137 11820
 26684 9817 16867
 22928 8136 14792
 15012 5213 9799
 17130 9529 7601
 8614 4476 4138
 6645 4267 2378
 5666 3495 2171
 6055 3948 2107
 7486 4923 2563
 5102 3322 1780
 4542 3042 1500
 5611 3982 1629
 4646 3199 1447
 6150 4433 1717
 6942 5076 1866
 12189 9187 3002
 5974 4394 1580
 6988 5287 1701
 5161 3881 1280
 8240 6304 1936
 7349 5624 1725
 4930 3823 1107
 7293 5646 1647
 5326 4150 1176
 10257 8025 2232
 6091 4694 1397
 7958 6216 1742
 5947 4646 1301
 8100 6369 1731
 8067 6375 1692
 6633 5137 1496
 8872 7018 1854
 6712 5214 1498
 9864 7718 2146
 13931 10857 3074
 8655 6820 1835
 8497 6787 1710
 14694 11529 3165
 10493 8334 2159
 12713 10032 2681
 9161 7248 1913
 8960 7071 1889
 15530 12194 3336
 9191 7340 1851
 14786 11720 3066
 9929 7878 2051
 15189 12074 3115
 11751 9378 2373
 13915 11031 2884
 12928 10346 2582
 14602 11554 3048
 12786 10351 2435
 15247 12247 3000
 17644 14174 3470
 10156 8174 1982
 17228 13814 3414
 11053 8816 2237
 1264738 1020214 244524
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 3 1 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
2 0 0 0
0 5 1 0
1 0 0 0
21 0 3 2
112 1 6 2
293 1 7 3
768 5 22 8
1986 6 32 21
5616 16 54 36
14372 17 86 43
37717 27 112 103
82757 59 169 183
99393 99 241 267
58769 151 417 400
19412 247 560 530
4069 372 815 749
1553 536 917 982
1411 750 1160 1159
1634 1161 1666 1769
2041 1531 3742 3454
2168 1802 2089 2096
2593 2255 2480 2353
2994 2832 5465 4587
3282 3145 3240 3122
4831 4375 3580 3543
4104 3791 4250 4293
4275 4013 4072 4054
4478 4163 4249 4268
4619 4514 4546 4580
4628 4667 4545 4709
4669 4714 4817 4805
4852 4802 4748 4887
4926 4979 4967 4897
5054 5114 4991 4878
5062 5210 5110 5149
5376 5265 5257 5287
5491 5613 5544 5484
5744 5701 5685 5719
6121 6050 5969 5804
6276 6235 6367 6221
6593 6462 6516 6563
6821 6750 6738 6763
6977 7186 7125 7065
7375 7263 7143 7256
7226 7284 7250 7369
7240 7168 7331 7235
7179 7054 7058 7113
6984 6825 7041 6975
6653 6584 6475 6636
6349 6249 6340 6224
5819 5838 5862 5849
5455 5425 5421 5301
4901 5047 5011 5080
4633 4472 4613 4509
4041 4064 4172 4153
3932 3907 3775 3822
3541 3650 3676 3572
3397 3542 3515 3496
3419 3353 3425 3372
3342 3387 3396 3331
3477 3481 3485 3534
3989 3767 3953 3789
4149 4166 4098 4088
4582 4659 4634 4659
5024 5061 5130 5078
5844 5747 5889 5906
6349 6252 6331 6284
6604 6822 6666 6652
6997 6889 6845 6724
6872 6781 6851 6868
6180 6110 6153 6124
5193 5217 5148 5138
3706 3646 3539 3597
1843 1839 1948 1898
682 675 701 643
106 105 109 112
0 0 0 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 
];
