A = [
126542 125785 781261 113489 111821 107257 108055 105438 107619 104829 110117 125162 153629 177062 200418 226684 241473 249096 250826 247853 242024 239988 241667 235808 237033 280184 277868 272256 308582 255573 255226 249344 195073 197055 195047 196462 195489 192208 192122 194570 193744 194064 193817 197017 196577 197335 196270 194648 197683 196970 197320 196381 196151 196386 194292 193954 191519 193633 193497 189368 189797 191280 190238 189877 189633 188917 186987 185311 183954 182625 182248 182098 181705 180702 180476 180114 177420 176336 174430 172850 171673 170519 168566 168522 166439 165054 162445 159001 155797 155012 153709 153104 151426 150638 149026 148454 147200 145773 145670 143492 142707 140916 141229 139135 138511 137179 136238 134910 133902 133096 132435 131141 130158 130391 129036 128722 127941 132428 133807 133814 138841 140455 141642 141549 141863 141934 141364 140344 139869 138705 137636 137724 136010 136551 135818 135591 134904 134682 133858 132269 131640 130934 130279 129755 129388 128566 127417 126965 126047 125735 125570 124956 123885 123355 123358 122199 121662 120511 120411 120999 119373 119077 117144 116304 116046 116030 116035 113958 113522 113530 113493 112374 111627 111048 110399 110190 109882 109509 108610 107341 107343 106323 105983 105686 105638 105092 104734 104298 103249 103201 102913 102014 101336 100879 100720 99722 99718 99421 98839 99109 97946 98002 97000 96631 95894 95651 95002 94133 93472 93964 92125 91993 91916 91289 89755 90423 89233 89212 88742 88494 87555 86841 86556 85491 85807 85277 84152 83467 83128 81734 81143 79982 80004 78893 78225 78201 77347 77026 75927 75634 74414 74203 73127 73391 71955 71465 71184 70876 70070 69916 69155 68420 68141 67942 66774 66414 65887 65024 64549 64058 63438 63038 62679 61597 61297 60548 59785 59609 59006 58938 58132 57357 56962 56642 55780 54820 54386 54514 53331 52973 52815 52034 51737 51176 50365 50019 49601 49083 48307 47991 47459 47408 46745 46201 45458 44857 44841 43656 43706 43481 42376 41913 41326 41297 40784 39927 39495 39148 38545 38482 38163 37660 37104 36588 36286 35577 35137 34820 34283 33565 33667 32905 32901 32402 31929 31471 31096 30663 30037 29535 29409 29068 28666 28571 27945 27489 26927 26694 26016 26274 25950 25118 24971 25208 24144 24104 23432 23240 22977 22777 22585 22112 22150 21641 21306 21124 20576 20451 19592 19936 19430 18909 18739 18608 18404 18167 17892 17747 17302 17104 16746 16917 16404 16177 16014 15538 15415 15337 15159 14863 14590 14342 14066 13983 13618 13670 13244 13292 13114 12819 12496 12552 12214 12073 11707 11505 11458 11176 11179 11035 11049 10856 10589 10551 10054 10036 10158 9784 9694 9539 9451 9236 9103 8879 8851 8772 8536 8548 8346 8341 8148 8049 7925 7803 7595 7526 7527 7322 7224 7184 7000 6909 6750 6677 6625 6545 6418 6217 6170 6323 5977 5869 6025 5864 5638 5672 5679 5774 5346 5355 5340 5304 5202 5111 4975 4849 4853 4738 4821 4490 4560 4509 4430 4364 4295 4307 4188 4201 4285 3991 3961 3889 3884 3681 3756 3710 3574 3599 3461 3323 3477 3382 3322 3384 3136 3125 3161 2996 3029 2901 2960 2926 2905 2839 2828 2733 2760 2612 2567 2605 2647 2453 2463 2485 2399 2361 2453 2349 2245 2320 2209 2242 2064 2157 2070 2071 2043 2009 1956 2002 1913 1810 1841 1841 1778 1787 1699 1803 1547 1594 1714 1639 1532 1543 1640 1547 1503 1492 1392 1435 1463 1356 1397 1362 1325 1256 1261 1249 1281 1280 1195 1200 1148 1203 1080 1037 1085 1049 1045 1053 1075 947 1012 980 986 937 923 924 919 850 910 835 781 767 833 875 829 764 769 790 735 815 709 703 700 659 702 663 669 665 670 625 595 568 628 587 603 579 581 591 557 547 545 543 525 534 517 523 474 519 511 430 481 443 403 444 472 445 454 444 449 391 402 418 408 374 395 364 348 356 358 366 335 351 324 303 308 369 334 338 290 293 285 300 249 296 293 260 242 242 289 247 266 240 242 248 277 259 259 252 237 223 243 218 206 204 196 176 199 197 180 179 199 200 166 180 172 154 216 141 167 177 183 173 179 143 143 156 147 151 136 140 128 144 112 123 125 122 110 106 99 118 124 110 104 112 107 130 124 103 101 134 103 101 112 78 84 96 82 106 102 84 74 75 101 118 74 73 94 119 104 86 81 86 88 92 94 93 100 86 83 72 66 100 79 70 82 75 80 75 70 82 67 72 98 70 74 72 69 76 68 79 59 69 50 71 68 64 73 58 36 49 51 56 45 55 57 40 45 59 50 40 47 59 38 43 32 42 54 47 34 48 44 37 34 42 47 43 36 45 43 37 49 38 50 45 51 41 64 51 48 45 45 54 43 55 43 48 48 32 39 59 31 27 56 30 39 27 43 35 46 31 44 46 30 34 29 24 33 36 51 44 44 32 32 38 32 39 44 29 34 25 34 33 33 22 22 31 31 19 32 34 25 37 25 34 27 33 20 37 30 21 22 26 29 20 17 19 14 25 26 23 19 26 27 22 21 32 25 32 24 26 17 29 31 25 17 20 27 35 26 25 30 19 16 25 22 24 12 28 22 26 27 19 17 30 21 26 19 25 25 36 21 29 34 21 19 17 15 16 30 17 29 27 22 18 14 13 25 13 14 21 13 19 15 17 28 21 9 15 27 24 22 21 13 20 23 20 14 21 17 18 20 15 20 15 15 24 9 19 13 21 14 17 13 10 16 23 22 17 21 9 16 15 10 12 12 25 21 13 22 23 20 15 16 14 20 17 11 12 12 33 5 20 11 8 10 11 9 15 11 9 8 30 20 15 18 25 12 12 15 23 13 17 16 19 8 13 14 16 14 11 11 14 11 12 14 13 8 18 10 14 8 19 15 14 15 8 11 8 14 12 10 10 11 13 3 16 15 17 12 10 12 8 8 9 16 11 9 7 9 10 17 12 12 12 7 16 16 15 19 26 16 18 17 10 21 11 16 13 19 11 13 13 8 20 12 7 9 9 7 3 7 8 11 9 11 9 3 6 4 7 6 6 6 6 7 10 6 8 5 10 8 10 8 7 10 10 5 9 5 6 13 11 11 11 9 12 14 9 13 7 8 8 8 13 4 14 3 5 13 12 6 9 9 8 9 16 10 9 5 15 5 7 6 7 5 7 4 5 4 4 2 6 7 8 8 2 7 2 10 5 5 5 10 3 6 8 2 10 4 7 6 8 5 8 4 7 4 2 9 6 4 9 5 6 5 6 7 2 3 7 7 12 6 4 7 5 3 0 5 7 6 3 4 7 6 4 9 6 7 3 3 4 3 6 4 5 8 4 12 10 7 6 7 6 13 7 3 6 7 13 10 8 9 9 9 9 6 11 13 12 4 13 10 8 5 5 2 5 8 7 7 9 7 5 4 6 4 9 2 5 2 6 8 3 5 0 3 4 3 6 2 5 8 6 4 7 5 7 3 2 7 4 4 4 8 16 12 5 6 6 4 4 5 5 7 3 8 5 4 5 6 5 5 7 9 2 2 3 11 2 2 5 6 6 3 6 3 5 7 3 10 8 4 15 2 5 7 4 7 6 1 5 4 3 4 6 4 8 0 2 4 0 4 7 5 1 2 3 1 5 1 5 2 8 6 4 1 5 3 5 2 6 3 7 3 5 2 7 4 11 8 7 9 8 6 6 11 9 8 6 1 6 6 6 0 3 3 6 8 3 7 4 18 6 5 7 8 4 4 12 2 7 5 4 8 3 4 6 5 11 8 7 6 13 3 4 8 5 5 5 17 5 10 2 5 8 7 14 5 4 4 9 3 7 5 7 7 14 3 7 7 10 9 5 5 12 3 7 5 9 11 16 8 14 8 7 14 7 9 12 8 19 2 12 10 11 7 3 16 6 5 8 12 11 14 7 14 12 7 9 17 10 7 14 5 13 12 9 7 12 9 9 20 12 9 13 12 5 10 6 10 13 6 14 10 10 9 6 11 14 7 9 7 5 7 8 1 4 10 11 11 14 19 13 6 9 23 10 12 16 15 14 8 9 12 16 10 18 17 22 28 18 11 19 25 22 21 15 20 21 10 17 27 21 26 15 18 12 14 21 19 15 7 24 14 12 21 14 13 7 9 4 2 11 10 7 4 6 9 9 11 7 9 4 4 10 7 8 5 6 2 7 4 5 2 4 8 8 4 7 4 4 2 11 9 2 10 1 8 2 12 7 2 5 7 8 1 5 5 9 7 5 5 11 5 2 6 8 4 4 4 3 7 6 6 7 6 5 2 3 5 0 7 9 3 2 7 5 8 7 2 4 7 2 7 2 3 6 1 6 0 1 3 0 1 3 1 2 4 1 3 2 5 4 1 6 6 3 6 3 2 2 2 6 2 2 3 2 2 2 1 0 7 6 3 2 0 3 4 4 1 2 0 2 2 3 0 4 5 1 3 2 1 2 1 2 0 2 3 0 0 1 1 1 0 0 0 4 0 0 2 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 2 0 2 4 1 0 1 1 0 0 1 0 0 2 0 0 0 1 0 2 0 4 1 3 0 0 0 1 3 2 0 1 0 0 1 1 1 0 1 1 0 2 0 2 1 0 0 2 0 0 0 1 1 1 0 0 0 1 2 1 1 0 1 1 0 0 0 1 0 1 2 1 2 2 1 2 0 0 0 0 0 1 0 1 1 1 0 3 0 1 0 0 0 5 1 0 0 0 3 0 0 2 1 2 3 0 2 1 2 0 1 4 3 2 1 0 2 1 3 2 4 0 1 0 2 1 1 1 1 3 2 0 0 0 1 1 2 2 1 1 2 3 1 0 1 1 0 0 3 0 0 0 2 2 0 1 0 5 1 2 2 1 0 1 1 1 0 2 3 0 3 2 3 2 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 2 1 0 0 1 1 0 0 0 0 1 0 2 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 2 0 0 2 2 1 
];
B = [
0 0 0
 56949 42177 14772
 147524 113203 34321
 94373 73529 20844
 73175 56585 16590
 61176 47904 13272
 48319 38026 10293
 44605 35433 9172
 48469 38968 9501
 53692 43389 10303
 96071 78029 18042
 60921 49321 11600
 53136 43605 9531
 50414 41185 9229
 48253 39372 8881
 80174 66158 14016
 61357 50260 11097
 61216 50695 10521
 54857 45314 9543
 57845 48042 9803
 74814 62325 12489
 66266 54921 11345
 66015 55070 10945
 65275 54552 10723
 64522 53782 10740
 76679 64245 12434
 67020 55925 11095
 72203 60586 11617
 65288 54791 10497
 70572 59188 11384
 74763 62926 11837
 74001 62306 11695
 73454 61834 11620
 70271 59239 11032
 84088 70864 13224
 74798 62946 11852
 75404 63491 11913
 150236 126899 23337
 73907 62282 11625
 87400 73803 13597
 141048 119492 21556
 86264 72838 13426
 132191 111858 20333
 76022 64350 11672
 88068 74560 13508
 137276 116363 20913
 91347 77530 13817
 134487 113891 20596
 89033 75419 13614
 133711 113093 20618
 91020 77087 13933
 134041 113562 20479
 95259 80553 14706
 134418 114038 20380
 92742 78618 14124
 143100 121407 21693
 127924 108468 19456
 88666 75293 13373
 130908 111086 19822
 71394 60373 11021
 16154238 14084264 2069974
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 8 0 0
0 3 1 0
1 1 0 0
2 2 0 0
3 0 0 0
2 2 0 1
3 3 0 0
2 2 0 0
11 6 0 0
34 7 0 0
77 12 0 0
202 12 1 1
578 23 31 13
2702 33 171 60
16421 109 257 142
114752 153 388 295
494489 345 662 598
939989 784 1532 1422
792099 1673 2871 2959
372699 2759 4833 4878
149951 4292 6975 6974
40662 6378 8876 8893
14884 8789 10878 10819
14212 11546 13342 13194
16538 14639 15971 15723
19790 17962 19078 19282
23620 21575 22578 22706
27500 26194 26481 26921
31776 30449 31141 31048
36163 35328 35618 35502
40941 39687 40503 40651
46324 46358 45564 45594
51500 50705 50173 50834
56300 55346 55881 55440
61357 59562 59704 59680
66465 63093 63338 63393
67340 66717 66963 66908
70098 69342 69186 70264
72443 72242 72402 72886
75546 75159 75795 75358
78838 78293 77994 78233
81344 81415 80905 81222
84613 84431 84019 84470
88544 88421 88272 89412
93358 93190 92550 93777
97843 98398 97530 98121
103005 103169 102866 102831
108006 107918 107231 108028
111865 112329 111564 112868
115071 115568 114984 114454
117304 117425 116297 116752
115715 116939 116168 116571
113452 113588 113255 114058
109756 110278 109890 110003
104088 104383 104279 104293
96643 96793 97112 97081
88809 88758 89104 89061
80705 81390 81513 81629
73596 73842 74279 74129
67685 67851 67769 67962
63124 62849 62948 62790
59221 59908 59694 59987
56525 57110 56434 56689
57023 56614 56669 56560
57891 58110 58484 58295
60766 60843 60536 60881
64961 64536 64936 64949
73951 74589 72078 71593
76172 76202 75895 75937
80032 79998 79806 80054
80493 80505 80157 80710
79002 78594 78109 79268
71803 71838 72060 72265
60106 59740 59568 60407
48136 48196 47650 48077
36759 36836 36957 37048
26592 26839 26575 26648
17919 18119 18317 18526
13338 13470 13623 13680
9652 9804 9638 9801
6786 6711 6595 6792
4195 4203 4093 4348
374 394 394 399
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
