A = [
1303039 1287045 6266291 1332973 1360257 1300136 1261923 1362439 1336439 1394045 1572571 1892198 2375255 2832990 3216079 3515628 3900213 4233847 4194502 4095985 4263408 4356008 4238535 4124800 4162259 4632165 4653929 4571833 4803768 3587437 3483060 3287087 2096929 2094951 2059294 2040744 2016699 1943117 1938353 1925499 1893191 1894600 1880594 1868188 1876185 1837522 1812577 1839910 1791779 1771821 1769355 1705756 1714621 1699526 1665807 1632675 1635354 1644803 1585850 1548434 1553505 1525860 1499067 1475309 1455168 1450044 1422882 1395694 1386439 1359182 1349166 1348705 1332154 1328712 1337114 1319653 1309237 1300608 1277949 1254122 1240326 1228629 1203584 1186846 1181148 1150923 1124407 1089175 1063943 1051443 1031442 1012130 1003285 985275 970258 960835 947384 935819 921933 905175 896610 881621 865677 853680 842840 833240 823570 809172 797811 790498 779047 777177 768005 758054 756772 750824 947439 953412 944625 1136610 1145930 1133047 1116089 1101280 1078568 1062779 1045191 1027143 1009101 993686 973233 955748 936908 919347 904928 887880 870186 859360 842160 827114 812744 799824 783572 771408 756472 741525 728313 715252 702150 690074 677134 664828 653001 638508 624501 615690 602216 591700 579134 570746 559572 550102 538441 528799 517603 509267 501651 491287 483469 475344 465655 458047 448922 441337 433672 426052 418362 411000 403441 396470 388112 382244 376650 369453 363565 357859 350555 344808 339163 333476 329628 322555 317891 311329 307102 300785 296210 291346 285922 280879 276364 273047 268636 262841 259346 253867 250576 245353 240922 237359 232804 229339 224787 220849 217768 215438 210345 208354 204483 200656 198309 194012 191296 188574 184331 179875 176264 171727 167515 164648 160753 157035 154759 151607 148951 145873 143918 140333 138138 136210 134124 131372 128815 126827 124332 122376 119797 117797 116085 114142 111632 109933 107911 105987 103670 102620 100661 99070 97190 95433 94437 92142 91149 89159 88270 86374 85067 83671 81983 80455 79004 77914 76632 75434 74264 73036 71183 69503 69172 67637 66721 65634 64434 63260 62365 61658 60334 59580 58344 57922 56190 55434 54307 53666 52549 52092 51003 50209 49288 48544 47706 46486 45891 45306 44461 43699 43355 42506 41767 40726 40144 39470 39048 38132 37639 37204 36374 35736 35100 34504 34159 33655 32524 32213 31489 31335 31095 29871 29777 28906 28946 28330 27913 27444 26778 26456 25946 25595 25072 24775 24191 23897 23695 23082 22977 22073 21906 21545 21134 21024 20677 20441 20226 19584 19179 18847 18432 18486 18066 17866 17759 17053 16647 16566 16313 16076 15699 15453 15266 14920 14934 14737 14301 14090 13867 13446 13489 12911 12880 12770 12542 12260 12092 11886 11807 11483 11172 11254 11077 10971 10455 10379 10208 9961 9863 9704 9534 9437 9300 9117 9156 8738 8695 8420 8384 8247 8203 7944 7932 7682 7666 7464 7439 7396 7128 6816 6750 6760 6530 6601 6572 6316 6427 6186 5945 5980 6022 5960 5745 5622 5372 5542 5333 5249 5200 5041 5081 4930 4888 4789 4739 4580 4488 4479 4419 4341 4264 4194 4076 4003 3970 3890 3764 3889 3698 3667 3760 3584 3517 3371 3389 3335 3259 3352 3207 3160 3207 2887 3038 2937 3029 2850 2840 2796 2794 2783 2577 2694 2520 2555 2552 2428 2356 2499 2342 2382 2228 2183 2158 2141 2129 2096 2064 2026 2025 1971 1894 1945 1793 1924 1851 1854 1783 1713 1776 1692 1657 1578 1625 1600 1613 1527 1585 1467 1493 1491 1402 1485 1352 1462 1323 1275 1284 1219 1298 1218 1115 1259 1200 1158 1152 1181 1155 1080 1133 1121 1098 1055 1006 984 1005 945 948 1023 957 926 942 943 896 877 843 951 828 831 830 788 807 818 812 805 756 725 717 750 723 716 667 667 678 668 678 686 665 611 597 621 609 568 596 580 548 582 545 553 577 515 509 525 511 527 502 495 489 535 508 455 467 517 463 451 478 453 435 436 416 382 386 401 415 389 396 430 405 383 377 392 353 375 365 384 363 364 372 349 326 344 310 350 328 311 318 307 296 309 295 285 290 290 300 296 270 283 280 253 297 271 260 267 247 243 257 274 258 235 251 287 233 263 232 231 241 225 225 216 236 219 217 228 193 221 221 217 208 211 210 202 201 188 201 204 188 202 180 196 178 195 174 173 183 195 167 151 189 164 205 155 155 171 186 163 152 165 147 168 151 194 168 159 166 166 158 152 144 147 159 124 164 134 137 162 139 129 130 125 136 117 116 129 126 122 141 144 125 125 127 106 108 143 123 115 127 118 102 120 100 125 109 105 111 105 114 103 117 84 90 103 118 104 104 93 89 99 111 113 106 108 78 100 106 93 85 95 75 94 95 91 94 100 90 89 86 101 77 100 84 80 91 76 93 83 81 91 80 90 92 60 78 72 75 82 76 65 72 80 100 93 67 69 87 79 80 65 70 67 85 98 63 76 58 90 78 72 70 79 67 66 65 80 76 71 61 56 64 72 60 63 49 44 62 53 59 68 67 65 61 55 73 65 53 87 52 68 58 67 64 62 48 59 57 54 43 61 58 54 47 50 50 60 49 69 52 46 38 56 53 44 42 38 48 44 48 57 54 59 40 51 64 43 45 45 59 42 44 35 38 49 32 51 42 37 39 36 41 54 50 48 45 45 51 52 37 49 37 39 45 53 27 41 40 49 40 29 34 52 42 50 29 44 37 45 31 31 38 31 48 40 33 34 35 40 33 41 30 30 46 38 46 40 26 24 41 25 25 37 38 32 38 33 38 21 39 31 31 35 31 22 24 33 35 29 40 31 20 28 33 26 26 28 26 30 32 28 26 32 26 24 17 21 27 22 32 20 28 27 31 30 22 35 15 27 30 23 22 31 30 28 28 21 23 21 22 36 28 29 30 32 28 27 35 27 27 17 23 21 28 30 22 24 22 18 22 22 22 20 16 22 24 25 32 20 24 24 30 15 20 14 19 27 22 16 26 24 26 22 24 37 22 31 34 25 25 25 29 23 40 17 23 27 16 34 24 30 29 37 37 29 46 26 46 26 26 33 33 48 28 39 33 30 36 29 33 42 41 35 37 35 42 28 46 29 46 31 33 27 31 39 38 35 28 34 25 30 29 29 33 312 33 37 32 39 31 31 27 18 18 28 18 20 21 29 30 22 24 26 24 33 19 31 17 26 9 25 24 16 11 24 13 14 14 19 20 18 17 16 14 18 10 20 18 8 26 25 21 22 12 25 23 17 10 22 11 20 18 21 19 21 25 19 31 30 25 39 87 52 272 11 13 7 10 11 8 8 7 7 12 14 8 10 14 9 10 9 12 8 10 5 9 12 9 7 10 15 13 12 10 6 9 22 10 14 4 11 18 11 7 10 12 7 5 16 12 11 16 13 11 14 10 8 9 11 12 8 8 14 9 16 12 19 11 13 9 13 21 14 14 17 15 18 21 18 7 18 14 22 15 24 15 11 18 14 21 19 13 20 16 25 15 20 20 18 20 22 24 27 22 14 16 12 21 20 18 17 20 23 18 21 21 24 15 23 21 13 24 19 22 21 25 35 13 14 18 32 20 21 20 10 5 24 21 13 13 23 19 11 5 13 5 4 8 11 9 7 7 4 6 8 14 4 0 5 7 4 7 5 12 4 7 5 3 15 7 9 6 6 6 8 6 5 5 5 13 7 6 4 9 15 8 9 6 7 9 7 9 7 7 7 6 6 9 5 12 6 7 3 5 9 5 9 4 4 5 9 9 9 13 3 5 10 5 7 5 8 10 3 8 3 4 4 11 8 6 6 8 10 7 4 6 9 4 9 12 7 3 3 10 7 4 3 6 5 5 5 2 8 11 5 7 3 4 6 2 10 3 3 7 8 4 4 6 9 7 3 6 7 4 5 1 3 3 4 3 6 5 5 5 5 8 4 9 12 7 5 5 5 10 4 5 5 3 7 6 7 4 5 7 6 5 3 0 2 5 5 1 3 5 7 4 5 1 5 5 3 1 4 1 1 6 7 5 4 4 2 4 5 5 3 2 2 5 6 2 8 3 5 4 5 6 3 6 6 3 8 8 5 5 4 1 8 7 9 3 1 5 4 7 4 5 8 7 7 1 4 3 8 3 4 5 5 4 1 6 8 12 12 6 7 9 4 10 7 8 7 6 8 4 6 3 9 7 5 9 2 5 5 3 9 5 7 6 5 5 7 5 6 4 3 4 7 5 6 5 6 4 3 6 5 5 5 4 4 3 4 0 7 3 3 4 0 5 2 5 0 3 1 1 1 6 6 5 2 4 5 5 2 2 2 9 2 4 4 4 5 3 3 2 1 4 2 0 4 5 2 5 0 3 1 3 7 3 2 6 1 3 2 2 4 2 4 2 2 3 1 3 4 2 1 3 2 0 2 1 2 6 2 1 4 2 1 1 1 2 4 2 3 3 0 2 4 0 0 1 1 1 3 3 0 1 1 3 2 1 0 1 1 2 0 2 1 1 3 1 4 0 2 1 1 1 2 1 1 1 1 3 3 4 1 1 2 0 2 3 3 2 1 4 0 0 3 1 0 3 3 1 1 2 1 2 1 0 2 4 0 0 2 1 2 1 2 1 0 2 2 2 2 0 1 3 1 2 2 0 2 0 2 1 2 1 2 1 0 0 3 1 2 0 0 2 2 2 2 2 0 0 0 2 1 0 3 1 3 2 1 1 2 0 1 0 1 0 6 1 2 3 3 1 0 2 2 1 1 0 2 0 0 4 1 0 1 0 1 0 1 2 3 1 0 1 1 1 1 1 2 0 0 0 1 2 1 1 1 1 1 0 0 0 0 0 0 0 0 2 4 0 3 0 1 1 1 1 1 2 1 1 0 1 0 0 1 0 0 0 0 2 0 4 1 1 0 0 2 3 3 1 1 1 3 4 1 2 1 1 0 0 1 2 1 1 0 0 1 0 3 1 0 2 2 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 3 1 0 0 0 1 1 1 2 0 1 2 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 0 2 3 0 0 1 0 0 1 0 0 0 1 0 0 0 2 0 1 1 0 0 1 0 0 1 3 0 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 878365 711307 167058
 909678 740598 169080
 871161 709927 161234
 842222 686621 155601
 1065733 874157 191576
 847850 693958 153892
 864800 708035 156765
 2223562 1831489 392073
 822814 675347 147467
 993692 820504 173188
 1784540 1474850 309690
 943768 780087 163681
 1588615 1317314 271301
 803111 662965 140146
 940808 781142 159666
 1597346 1329528 267818
 938695 781585 157110
 1527659 1275249 252410
 914498 762222 152276
 1470017 1230575 239442
 908827 760041 148786
 1445255 1213038 232217
 954261 802114 152147
 1428676 1203259 225417
 902635 759005 143630
 1515788 1283235 232553
 1334594 1129813 204781
 835730 706887 128843
 1339267 1138230 201037
 649670 550623 99047
 109514052 100737354 8776698
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
6 23 0 0
0 5 0 0
0 10 0 0
6 10 0 0
4 6 1 0
10 5 1 1
9 13 1 0
91 7 5 1
274066 21 1 3
2588124 22 7 7
4979891 31 20 11
8432040 45 64 29
11907754 84 414 160
14331693 167 1501 647
13485945 360 2158 1602
10704119 1309 5663 5236
6880240 3126 12394 12337
3836791 5869 22020 21565
1950303 10041 33485 33138
813887 15941 44817 45189
287446 23939 56741 56896
118071 35158 69212 69660
93846 51246 83037 83605
107416 70530 99627 99238
124626 93584 117164 118508
143804 118449 136744 137805
166200 143999 158120 157791
186916 168379 179163 179150
205974 189688 198006 198514
221390 207510 215657 215789
233318 221859 228389 228144
239962 231577 235011 235874
243454 236682 240258 242172
245723 241491 242682 243814
245912 242616 244510 245153
246327 244585 246333 245236
246802 246203 245465 247003
248783 247395 247653 247758
250076 248970 249678 250792
253071 252711 252743 254342
257799 256831 257237 257889
263147 261401 262145 264154
270865 269936 270059 271203
280913 280801 279554 281453
292619 291902 291803 292927
305374 304440 304543 306097
317407 317090 316050 317457
328840 328394 328505 330502
339918 340329 339503 339653
347237 347066 346986 348323
352818 352180 352359 351564
353327 353153 352503 354580
348540 348053 347375 350020
341924 342773 341347 342587
327926 329673 328350 330254
313822 314540 313280 313938
294808 296363 295927 296124
274377 273693 272374 274520
249074 249799 248193 250609
226376 225551 226451 226334
204173 204470 203442 204909
185443 185918 185199 186329
167166 166133 166114 167118
152958 153602 152660 153422
144688 144753 145039 145080
139504 139286 138671 139253
139030 138711 137910 139493
136544 136884 136146 137283
131539 131869 130827 132107
133873 133532 133640 133917
130207 129628 129456 129890
122650 121805 122118 122394
115244 115034 115432 115635
98582 99713 99072 98715
84018 83744 83683 84781
68521 68471 68477 68620
51241 51366 51282 51243
33259 33098 33419 33500
25320 25239 24929 25693
18413 18599 18712 18446
10558 10657 10518 10648
4968 5046 5056 4884
220 241 243 248
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
