A = [
1038695 995528 26249510 8293683 941474 1362860 8867170 1211284 1122134 1140298 1291885 1016880 994944 963479 970357 929593 876142 855464 848293 795354 785788 768030 722291 726173 746068 717269 708610 674531 616133 508735 493131 441482 307605 293004 272834 277666 269725 250929 258597 251532 261523 239841 231440 224054 227397 223785 217531 221071 214464 212026 216123 209770 202512 211215 206692 198308 203399 198469 195816 197615 193688 190984 193130 187136 186002 188845 183018 182478 183718 180825 178934 179947 178691 178501 178973 174618 172933 174656 171136 167695 171778 167916 164068 167743 163643 161658 164600 160741 161185 163093 157144 155317 159158 155261 152696 155256 152773 150888 153112 149627 148365 149703 146184 146795 150497 145795 143921 144515 145147 141103 145666 141633 139911 142924 139384 139629 144979 141905 141960 146279 142105 144328 145123 138947 139359 141145 138628 136674 139289 134892 136732 136055 132450 133485 138323 131368 131488 135260 130857 128271 131555 128196 126336 127792 126099 126669 126852 124250 124556 125783 122776 123408 123811 120749 120628 122274 120349 122093 123286 118033 120572 119352 117793 117734 118326 117452 115427 117230 115601 114713 114158 113564 114319 115226 113118 111713 114532 111595 112150 112137 109637 110671 110088 110480 114967 125586 114978 116492 115018 114022 110208 106103 104633 104763 106039 104628 104267 103795 103307 103304 104360 101953 102307 102596 100245 100242 101007 98901 100300 100536 100299 99271 99807 96995 97840 98027 97263 97303 98886 96201 94762 96810 95671 96049 96607 94166 95644 96150 94340 93189 93947 92272 91933 94178 92357 90889 92574 91155 90118 91473 90876 91763 91084 89101 88337 90884 87989 88043 89612 87882 87878 87207 86299 87241 85568 87880 84789 85390 83674 85722 84117 84202 83250 83978 83204 83319 82859 80877 81813 81889 80334 79803 79930 81417 79719 79520 78126 79091 78406 77662 78154 77002 77713 76261 76366 75646 74355 75945 73948 73564 74726 74209 72914 73428 71214 72999 71976 72187 71578 71117 70638 71681 70051 69650 69238 69481 68260 68193 68061 67936 67508 67942 66633 65667 67223 65441 66050 65714 64361 64566 63925 63037 64584 61092 62704 61292 61377 60505 60737 59665 60214 59922 59138 58549 59534 58709 57270 56561 58449 56935 56360 56360 56037 54433 54815 54797 54044 54319 52960 54016 53287 52901 51549 51923 51461 51208 51160 50292 50183 49911 50189 49861 48548 48383 48707 48252 47511 46604 46936 46428 46450 46151 45594 45725 45486 45579 44221 43906 43078 43615 42678 42498 42218 43024 41452 40898 41463 40796 40547 40667 40518 41236 39032 39062 39251 39346 38993 38279 38185 37390 37828 36938 36832 36384 35809 35642 35761 35253 33847 34940 34323 34267 33535 33490 32538 32892 32250 31396 31792 31371 30806 31687 30590 29583 30608 29372 29003 28692 28576 28435 28101 27711 28053 27977 27043 26673 26392 26718 25904 25647 25078 24678 25202 24800 24385 24224 23646 23589 23663 23442 22605 22807 22301 22722 22132 21623 20965 21224 21355 20713 20936 20294 20658 20770 19633 19674 19152 19312 18809 18260 17870 17840 17934 17882 17648 17222 17029 17198 16581 16957 16324 16494 15764 16291 15323 15107 15180 14684 14630 14433 14095 14110 13572 13722 13253 13194 12861 12803 12444 12338 12293 12032 11999 11891 11453 11620 11053 11092 10851 10769 10664 10198 10181 10062 10495 9806 9996 9440 9413 9053 9240 8897 8618 8583 8477 8200 7884 7691 8002 7467 7408 7725 7183 7125 6885 6795 6899 6661 6541 6559 6416 6266 6010 6303 5833 6042 5611 5572 5464 5646 5273 5258 5151 5160 4799 4821 4842 4697 4641 4496 4293 4254 4249 4156 4195 4107 4206 3886 3792 3821 3708 3601 3573 3408 3378 3310 3190 3242 3310 2930 2866 2875 2949 2843 3000 2771 2740 2950 2634 2791 2583 2333 2410 2530 2476 2273 2240 2344 2282 2035 2094 2095 2169 1933 2058 1983 1971 1917 2022 1840 1850 1742 1808 1748 1628 1788 1625 1527 1773 1536 1661 1442 1434 1483 1517 1639 1575 1454 2015 1424 1623 1526 1275 1298 1278 1294 1169 1187 1349 946 1066 1039 975 959 950 1061 1003 812 994 901 867 794 888 820 818 816 801 791 899 693 667 652 585 634 597 603 611 565 583 531 549 491 553 544 552 494 525 576 483 507 482 409 470 501 431 406 387 412 426 350 406 370 388 385 368 364 406 395 359 380 399 368 357 373 380 326 304 375 353 310 318 333 284 307 309 272 264 302 291 304 257 278 289 251 282 232 254 273 268 277 259 279 281 273 302 251 272 283 288 265 236 217 273 257 278 267 271 273 298 275 251 238 210 228 252 189 179 222 215 191 202 168 162 166 187 154 207 156 190 159 206 170 170 170 171 168 160 151 146 248 184 175 123 199 153 162 154 175 152 168 178 123 154 156 129 126 122 146 136 148 164 167 163 131 157 140 141 117 134 128 131 154 143 137 143 149 161 132 135 154 151 134 157 151 112 133 127 135 151 139 166 111 111 127 134 159 114 144 122 148 137 116 116 116 107 114 113 129 106 129 108 137 116 207 125 120 113 120 115 97 100 113 105 102 102 102 115 121 100 118 102 94 100 110 109 113 95 99 107 95 104 103 88 100 103 110 115 104 93 103 96 144 93 104 81 88 90 125 132 94 95 93 116 98 79 99 87 104 86 103 116 80 82 88 95 108 72 83 88 107 81 91 97 91 91 108 107 63 90 58 109 88 114 103 79 65 78 98 76 61 108 70 93 97 72 70 92 73 78 72 87 96 75 71 100 77 80 75 69 68 84 61 65 70 53 74 124 59 61 66 82 73 76 68 75 84 76 68 58 70 90 73 74 79 77 88 67 60 69 79 58 67 70 70 65 54 69 71 75 57 65 58 80 64 60 95 69 71 52 54 50 66 67 54 84 68 59 71 80 62 76 97 67 83 68 84 69 59 91 73 83 92 79 67 95 55 64 119 64 55 56 69 84 54 58 76 76 81 75 69 54 81 67 68 61 56 74 77 78 60 58 75 83 60 74 79 52 71 65 51 62 63 47 58 53 62 65 83 54 62 79 66 58 89 64 60 72 78 64 59 79 68 60 68 67 83 58 71 71 55 66 57 68 60 103 91 43 44 39 57 79 54 57 38 54 38 39 41 33 45 45 47 36 50 42 44 43 55 64 32 58 55 42 40 41 46 41 38 43 37 43 37 46 49 48 55 35 58 39 41 48 59 36 38 48 39 44 43 52 39 29 48 44 42 45 23 35 49 31 28 55 37 41 33 31 68 50 47 34 38 48 30 32 31 30 39 32 49 40 39 31 45 40 28 36 39 31 26 43 34 29 27 25 38 35 35 46 39 40 45 40 39 35 28 40 39 44 37 48 27 44 27 40 40 44 25 41 31 30 34 36 50 41 35 44 34 46 46 44 36 34 54 40 42 31 34 39 29 32 46 42 34 43 52 29 31 32 31 28 30 34 37 37 31 28 46 38 36 29 30 33 30 37 32 22 28 43 39 36 32 31 36 41 26 38 26 36 35 29 27 39 40 29 29 22 31 34 40 24 33 37 44 31 34 39 33 45 41 25 33 40 55 43 47 54 66 56 38 62 61 63 59 59 68 56 50 64 46 67 67 57 60 43 59 48 48 38 40 35 61 40 30 36 32 41 39 38 29 37 34 30 40 32 51 41 33 47 27 37 52 39 31 40 41 54 38 58 25 37 43 43 36 25 83 42 29 28 35 34 39 36 39 31 39 51 35 35 30 33 42 40 47 41 56 47 32 45 38 40 46 51 40 31 54 47 24 41 29 47 30 26 36 37 26 23 19 25 14 23 21 16 21 17 33 27 16 11 26 31 21 12 14 15 21 13 12 20 13 22 8 12 9 17 16 12 12 12 11 14 9 15 21 20 8 17 17 10 21 18 20 15 15 14 31 21 21 14 12 18 11 21 15 13 13 10 15 22 14 17 20 19 15 8 8 8 13 20 11 11 10 15 13 9 17 8 12 13 17 8 12 18 23 11 13 17 12 13 19 11 15 11 12 21 13 10 10 19 13 16 19 14 10 12 10 12 21 12 11 21 15 11 19 36 16 14 6 14 22 14 17 17 14 10 24 20 13 14 10 12 12 11 18 7 17 21 11 12 17 20 22 22 15 17 16 14 15 11 6 15 13 13 19 14 12 24 12 13 15 15 12 14 13 9 11 20 13 13 18 14 13 15 21 16 11 9 7 19 12 18 24 12 13 11 8 14 18 9 8 13 5 15 14 6 6 7 14 20 13 11 6 14 13 9 12 12 8 15 18 16 12 12 3 14 12 11 17 13 23 8 12 12 10 22 11 11 13 19 13 14 14 9 10 16 6 9 7 8 5 9 13 14 12 5 11 6 9 10 4 12 11 10 5 5 8 8 6 9 10 7 9 9 9 3 5 8 8 12 7 7 15 6 14 9 4 8 9 9 10 7 4 8 4 5 3 6 5 7 11 4 7 9 8 1 10 1 5 10 7 7 6 9 12 4 9 5 8 6 6 6 11 4 11 9 4 9 9 5 11 2 5 8 8 9 5 4 4 9 4 10 8 5 8 6 5 9 8 14 8 15 5 5 10 6 8 13 16 6 6 6 17 4 1 8 9 3 3 5 9 8 5 7 6 7 4 5 8 5 5 9 3 5 11 15 5 6 6 5 11 6 6 9 3 8 9 10 6 5 9 7 7 7 13 22 10 8 6 11 21 4 9 11 56 14 47 15 20 14 14 6 2 4 11 18 8 18 4 6 4 9 9 3 2 1 3 5 8 7 4 10 6 5 8 11 3 4 8 5 4 3 10 7 7 12 3 6 8 10 6 7 16 15 5 10 8 5 5 1 5 6 5 7 10 5 4 3 7 3 6 3 0 5 5 8 3 2 3 6 4 1 3 3 1 6 7 6 9 5 9 1 5 4 4 7 2 5 3 4 6 3 4 4 6 3 5 5 3 4 4 6 5 2 2 2 7 8 1 3 2 5 1 4 4 4 3 6 5 4 5 4 0 5 5 3 2 4 3 8 6 6 7 5 3 10 6 2 4 2 5 5 5 2 4 0 3 3 5 5 4 1 2 7 1 1 1 4 2 3 3 1 4 6 5 5 3 4 1 8 4 5 3 
];
B = [
0 0 0
 108577 91011 17566
 64000 51234 12766
 124020 101624 22396
 78955 65581 13374
 91640 75733 15907
 133257 112129 21128
 71225 60882 10343
 243609 212159 31450
 44001 37112 6889
 31874 27016 4858
 22503 19526 2977
 29591 25027 4564
 12994 10562 2432
 11450 9598 1852
 14747 12500 2247
 19047 16703 2344
 43177 37474 5703
 22067 19844 2223
 32631 28560 4071
 38780 35319 3461
 64448 59231 5217
 186186 167890 18296
 40462 37392 3070
 32638 29023 3615
 28235 24881 3354
 38109 32261 5848
 31826 27500 4326
 34377 31364 3013
 23806 20805 3001
 34034 31274 2760
 27424 25281 2143
 109362 100511 8851
 50057 47340 2717
 25899 24141 1758
 36368 33846 2522
 21413 19984 1429
 35829 32817 3012
 23581 22107 1474
 37136 34776 2360
 24295 22706 1589
 32994 31007 1987
 33861 32336 1525
 72249 67183 5066
 36531 34782 1749
 36405 34343 2062
 27863 26615 1248
 32767 31098 1669
 35331 33261 2070
 27518 26215 1303
 41742 39628 2114
 24590 23513 1077
 38707 36440 2267
 32179 30738 1441
 69919 65563 4356
 37131 35866 1265
 37313 35409 1904
 31712 30501 1211
 41842 38970 2872
 45673 43859 1814
 65005876 64156710 849166
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1864 6218 2 1
278 1264 0 0
222 1712 1 0
253 2306 0 0
249 2037 0 0
348 2586 3 1
1623 3417 6 2
4527 3782 3 10
11116 4424 11 10
27178 5690 24 22
47283 6477 43 51
91864 8269 168 171
175862 9665 5378 5238
376528 12185 20099 18518
833342 15474 28397 26646
1996729 19540 38120 36754
4485090 25619 48286 48042
8143699 35586 59554 60723
11333297 53926 74668 78728
9921255 79589 99383 106226
3576087 105530 128106 136624
533011 128255 151865 161542
229116 150902 177343 187886
246313 174166 201927 214955
272541 196768 223786 237204
294408 219713 245587 259473
312390 237979 265350 280177
324777 250762 275214 291495
321832 255802 278735 292841
313652 256334 274602 290102
303784 252632 267432 279965
288757 243355 255315 266622
271138 230629 238076 248448
247819 220722 225872 233649
222504 203725 210127 215783
203794 190802 194991 200629
186912 177840 179657 184831
172951 168149 167700 171191
158758 155181 156402 157600
146798 145348 146252 147427
137466 134872 135322 136861
128127 126440 126772 127698
117293 118048 116322 116976
108441 107357 108048 108444
102691 99463 100118 100040
93217 93300 96036 96938
84921 84531 83716 83704
76570 75998 76993 76673
68823 69517 69836 69490
62955 62381 63439 63131
61615 60887 60900 60104
52240 52234 52789 53276
48245 48122 52295 51868
47259 47156 46952 47338
44692 44291 44738 44020
40670 42478 41067 40735
39082 39437 39294 39231
36707 37022 36598 37087
38183 38736 37728 37532
35698 35400 37996 37425
35467 35397 34882 35571
34837 33736 34700 34090
34465 34623 36157 36998
33684 33364 33080 33273
31938 32505 33933 34439
27322 27687 30017 32700
22553 22795 24279 23971
18734 20006 19989 21811
18747 18340 16574 22723
21140 16670 13980 14888
20354 22815 6871 6851
2041 2389 11931 12965
1 1 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
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
