A = [
45275 45679 241370 43054 37886 36043 36292 35571 38189 39429 42010 45993 49232 52772 56759 61342 66321 71305 76802 81698 86682 91903 97501 101550 105381 112738 112871 112399 115855 104392 104057 101824 88053 86510 83331 80060 76806 71832 69266 66288 63233 61257 59053 57689 56291 55126 54084 53047 52511 52198 51836 50933 50598 50177 49928 49463 49364 48796 48600 48040 48713 47907 47873 47797 47370 47524 47457 50657 50546 50783 53987 54306 54059 52989 53038 52747 52512 51999 51680 51668 51297 51081 50075 50101 50504 49853 48866 48505 48289 47519 47417 46974 46368 46544 45963 45699 45289 44707 44059 43779 42752 42836 42326 42379 41522 40996 40713 40221 39812 39132 39086 38319 37983 37478 36841 36494 36376 35653 35151 34970 34535 33916 33558 33121 32328 32555 32018 31418 31079 31013 30355 30037 29349 28919 28662 28055 27662 27456 27061 26954 26282 26053 25602 25418 24786 24329 24098 23564 23667 23131 22848 22437 22074 21682 21526 21302 20726 20244 20177 20060 19841 19391 19115 18687 18368 18199 18146 17895 17367 17259 17008 16586 16230 16182 15940 15941 15581 15447 14939 14656 14398 14333 14003 13599 13614 13503 13039 13062 12648 12579 12208 11962 11976 11683 11456 11086 10917 10800 10576 10665 10233 10155 10097 9969 9748 9402 9359 9242 9244 8981 8741 8866 8702 8380 8335 8158 7855 7914 7692 7695 7391 7478 7393 7141 7148 6895 6876 6773 6507 6512 6412 6187 6233 5840 5741 5828 5710 5718 5558 5579 5447 5300 5098 5250 4935 4948 4805 4978 4745 4714 4487 4425 4331 4240 4294 4244 4174 4126 4019 3901 3848 3888 3798 3754 3765 3570 3500 3674 3552 3664 3501 3508 3459 3520 3693 3332 3121 3029 3064 3007 2911 2833 2926 2728 2704 2711 2586 2514 2485 2531 2405 2385 2379 2321 2355 2325 2285 2229 2163 2162 2084 1988 2049 1988 1991 1904 1868 1810 1838 1708 1705 1690 1728 1704 1653 1625 1639 1580 1517 1521 1497 1512 1465 1496 1450 1372 1398 1394 1311 1302 1338 1386 1260 1272 1217 1217 1185 1101 1148 1180 1140 1092 1167 1089 1053 1075 1069 1013 1003 974 958 938 938 971 903 914 906 902 876 889 837 765 854 824 784 837 756 820 780 728 724 747 725 670 720 714 682 659 627 660 617 680 652 663 589 578 614 599 582 572 543 541 577 584 561 532 546 548 494 521 515 485 538 459 468 476 448 417 467 443 448 442 437 440 439 402 428 424 395 414 400 415 395 380 390 377 402 351 377 369 384 374 361 314 343 309 357 333 353 319 351 294 290 327 294 327 333 286 283 273 287 296 284 287 270 266 296 268 282 258 257 299 248 258 275 225 236 257 249 253 214 240 296 240 266 253 219 244 214 245 232 217 222 211 210 218 244 214 204 197 225 225 198 240 211 225 213 185 185 191 192 179 183 166 174 166 170 201 172 169 193 192 205 158 183 178 190 157 190 155 134 153 174 152 149 161 168 147 161 140 124 155 124 160 162 130 150 157 169 151 159 158 148 143 142 137 140 137 167 130 130 151 155 132 156 134 143 113 124 126 122 116 131 114 150 123 138 118 101 110 123 108 119 123 130 115 119 127 119 110 102 113 133 105 132 104 106 120 111 113 99 107 113 111 105 107 104 100 118 107 112 110 91 94 96 119 96 89 117 88 88 102 73 92 86 91 98 85 89 78 104 94 80 97 89 91 102 92 94 87 102 94 77 83 69 91 106 101 85 90 71 82 94 98 72 82 85 86 84 79 85 81 78 98 87 77 89 73 88 68 76 74 85 70 76 65 77 68 83 80 68 70 68 72 70 71 77 76 63 79 79 72 61 66 70 65 68 73 65 58 63 68 68 70 47 69 67 57 71 61 57 53 55 63 57 65 60 80 62 58 51 60 63 41 57 50 57 73 44 53 65 56 51 58 62 49 51 61 46 58 62 55 53 49 60 51 38 49 51 53 52 58 62 47 60 54 50 45 45 50 41 46 59 65 44 35 42 56 48 41 42 46 34 56 50 35 45 41 48 27 38 46 43 50 35 52 43 41 46 70 88 106 102 110 97 107 109 127 100 97 121 123 130 150 136 136 134 94 84 100 80 97 94 124 85 78 92 84 91 72 79 92 82 50 63 54 32 31 35 40 44 33 34 49 42 30 32 38 29 37 36 45 32 37 43 29 47 39 33 37 32 32 47 50 35 39 26 32 34 25 29 26 38 22 34 24 32 30 33 28 30 31 35 26 35 32 37 36 45 36 31 25 34 40 25 25 25 22 36 36 51 51 37 34 35 34 36 41 29 47 27 47 50 54 62 57 51 48 79 106 55 100 116 145 171 183 163 201 182 245 233 190 184 120 113 106 50 28 24 33 41 31 36 45 38 44 56 45 53 42 55 49 48 41 46 45 49 34 48 34 36 37 39 35 43 34 47 41 37 21 32 22 32 22 14 23 25 19 21 21 27 13 22 17 23 19 27 25 16 26 22 28 22 14 18 20 28 23 24 20 17 18 16 24 22 22 27 24 23 20 15 18 24 18 14 28 18 23 24 18 20 25 20 28 18 21 17 28 25 27 15 23 20 27 23 20 15 19 19 30 16 16 28 31 36 30 32 49 37 65 53 67 42 53 41 45 39 39 52 42 41 38 51 29 50 37 41 39 40 30 32 34 29 38 22 37 43 38 21 25 16 19 21 29 14 19 21 13 30 18 17 21 23 20 16 21 11 18 11 15 9 9 18 13 10 10 9 12 14 11 6 11 7 10 13 9 8 11 8 9 14 8 14 6 10 11 8 3 10 10 4 9 12 11 5 7 8 11 15 17 8 16 10 8 10 7 12 15 7 4 8 9 10 9 8 11 8 12 11 9 7 11 9 8 9 9 8 11 6 13 8 9 6 3 14 7 14 8 5 10 8 8 7 6 3 11 14 4 5 12 8 7 8 10 4 11 6 8 5 8 8 12 8 4 6 9 6 9 3 6 2 5 10 9 6 9 7 3 5 6 8 6 9 11 6 12 6 5 6 6 5 7 6 7 7 3 4 5 5 7 5 4 4 11 4 2 9 8 3 3 5 9 7 8 10 4 5 4 5 1 6 3 9 7 8 5 2 6 6 8 5 7 8 1 6 6 7 10 6 5 2 1 4 3 0 4 2 8 2 4 4 1 5 4 3 6 6 6 1 4 4 3 6 2 7 3 7 5 3 3 1 7 2 9 3 6 3 4 3 1 2 5 4 4 5 4 5 4 6 8 5 7 3 4 5 2 1 3 8 3 3 2 4 4 2 6 9 3 4 5 3 4 3 3 1 4 2 4 6 5 2 3 5 1 3 5 4 7 2 5 7 5 2 3 7 4 2 5 5 7 4 3 2 5 2 3 6 7 3 0 6 4 4 4 1 6 3 2 6 1 3 3 2 2 1 3 1 3 3 1 2 3 2 1 4 4 2 3 4 3 2 4 1 4 2 2 5 2 4 3 2 2 4 0 6 4 6 3 4 1 2 5 5 2 4 2 2 1 1 3 1 6 3 2 6 2 3 1 2 3 1 7 5 3 6 0 0 0 3 4 0 1 0 3 0 4 2 2 3 3 1 1 3 3 0 4 5 1 3 3 2 3 0 3 3 2 2 3 3 1 1 1 3 4 2 6 3 3 1 0 1 1 2 4 0 2 5 2 1 3 3 1 1 1 2 5 2 5 2 1 4 2 0 2 4 2 2 4 2 2 2 0 2 1 0 2 4 1 1 4 3 1 2 3 4 0 1 3 7 0 0 1 1 1 1 2 7 1 1 1 2 1 2 1 0 1 2 2 3 0 1 2 1 6 0 1 3 2 1 1 3 0 1 1 1 2 3 4 1 2 1 3 2 0 4 0 0 4 1 1 1 1 1 0 2 0 2 2 1 0 1 0 1 1 1 2 0 2 4 0 0 1 1 1 3 0 2 1 2 5 2 1 1 2 2 2 1 0 0 2 2 1 0 3 3 2 0 0 2 0 0 1 1 1 2 1 0 0 0 2 0 0 2 4 3 1 3 1 2 0 2 0 1 1 0 2 0 0 0 0 1 1 3 0 0 1 3 3 2 3 0 0 2 1 1 1 1 2 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 0 0 2 0 1 1 0 1 1 0 1 2 2 1 1 0 0 0 3 0 0 0 3 1 2 0 0 0 2 1 0 0 0 1 3 0 0 1 0 0 0 0 0 1 0 0 0 0 2 0 1 2 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 2 1 1 4 0 0 0 1 0 3 1 0 0 1 0 1 1 2 0 0 0 1 0 3 1 1 0 2 0 0 3 0 1 0 0 0 0 1 0 0 0 0 1 1 1 2 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 2 0 1 1 0 1 1 0 2 0 0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 3 0 0 0 0 1 0 0 1 0 1 0 3 0 0 0 0 0 0 1 1 0 0 0 2 0 0 0 2 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 2 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 
];
B = [
0 0 0
 23263 12489 10774
 26492 14500 11992
 23069 12813 10256
 37671 23918 13753
 27530 17797 9733
 20392 13737 6655
 18066 12237 5829
 13409 8973 4436
 11033 7609 3424
 7612 5194 2418
 8805 6096 2709
 10052 6891 3161
 10230 7088 3142
 23624 17080 6544
 16434 11960 4474
 16564 12400 4164
 15300 11722 3578
 15276 11780 3496
 15928 12230 3698
 13766 10484 3282
 19344 14733 4611
 17457 13211 4246
 16333 12488 3845
 14744 11302 3442
 16418 12593 3825
 16035 12449 3586
 19162 14754 4408
 14829 11599 3230
 18136 14079 4057
 18062 13888 4174
 16932 13127 3805
 19002 14644 4358
 18611 14469 4142
 23439 18105 5334
 18440 14326 4114
 20978 16297 4681
 42232 31998 10234
 19533 15235 4298
 23905 18427 5478
 38359 29137 9222
 24605 19113 5492
 36426 27661 8765
 20798 16242 4556
 25314 19736 5578
 38553 29654 8899
 25275 19805 5470
 37661 28946 8715
 26559 20773 5786
 38496 29649 8847
 25591 20123 5468
 38063 29410 8653
 29124 22667 6457
 38735 30208 8527
 27007 21282 5725
 41730 32603 9127
 38958 30497 8461
 27135 21564 5571
 39853 31286 8567
 24328 19691 4637
 3357159 2845378 511781
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
4 9 0 0
0 1 0 0
1 0 0 0
1 4 0 1
0 3 0 0
3 8 0 0
2 4 0 0
29 5 0 2
417 6 1 1
6552 11 16 2
28440 9 107 16
92977 6 157 46
224943 13 182 86
368870 28 213 138
404258 43 284 261
336553 61 449 433
224151 143 586 557
123125 233 866 787
54384 355 1092 1114
17885 575 1515 1556
5147 793 2013 1917
2778 1071 2375 2503
2927 1701 2899 2851
3252 2228 3405 3451
3863 3088 4049 4183
4582 3891 4781 4855
5355 4768 5422 5350
5957 5661 6587 6764
6689 6147 6989 6871
7746 7221 7651 7668
8039 7713 8311 8017
8437 8114 8402 8292
9017 8515 8652 8801
8620 8766 9083 9067
8795 8923 8942 9087
9211 8891 9089 9142
9027 9203 9303 9119
9231 9070 9535 9186
9213 9184 9388 9380
9417 9523 9716 9797
9833 9725 9875 9649
9774 9903 9899 9969
10311 10208 10205 10438
10775 10567 10497 10477
10811 10860 10984 10971
11363 11262 11230 11364
11749 11767 11746 11758
11758 11946 11853 11980
11992 12049 12047 12153
12309 12259 12212 12089
12115 11887 12260 12290
11933 11910 11940 11972
11366 11316 11354 11461
11051 11094 10844 10850
10409 10492 10456 10399
9777 9699 9737 9630
8933 9199 9151 9119
8363 8382 8285 8336
7559 7729 7656 7664
7041 7180 6987 6845
6431 6589 6542 6555
6134 6076 5902 6245
5878 5814 5770 5939
5691 5732 5663 5623
5567 5632 5782 5693
6153 5911 6032 6183
6414 6608 6601 6486
7257 7043 7121 7002
7730 7755 7816 7959
8861 8915 8736 8697
9919 9925 10027 10053
10583 10494 10736 10694
11296 11260 11266 11422
11658 11771 11705 11691
11690 11441 11458 11425
10345 10379 10323 10565
8634 8718 8606 8784
5975 6038 5972 6118
3071 3185 3041 3168
1239 1218 1207 1229
182 180 194 186
1 2 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
