A = [
148206 143994 776797 149805 146408 136315 135815 135903 143155 135764 143903 151365 167282 184136 208362 234315 239810 252154 258259 248560 235617 228304 223505 219978 217956 262066 263809 262196 293541 248459 251693 246262 203781 205356 206769 206763 203596 199108 197235 196050 197173 196634 195527 202183 202037 200129 200365 197205 202468 201144 198274 197307 200814 202261 199705 200100 194365 199453 197909 188404 187685 190480 189645 187934 188146 190075 188538 187528 186980 184852 187247 190517 190862 191241 193054 194229 191559 190416 185878 183354 180728 179222 177149 175869 175689 173954 171095 167117 164994 164855 162669 161068 160794 159725 158719 158669 158100 157440 156423 154292 153108 152267 150879 149459 149534 150007 149284 148488 147368 145640 144720 143180 142945 142484 141552 141828 141737 141465 140620 139228 138124 137408 137297 136061 135824 135483 134783 133644 133047 132522 131214 130748 129908 128811 128177 127876 127146 126278 126994 125601 124439 124014 123753 121460 120961 120627 120552 119616 119509 119626 118963 117610 117411 115643 115619 114667 114222 113480 113325 112061 111621 110560 109324 108785 108414 108133 107429 105961 106799 105715 105235 103886 104189 103869 102630 102700 101913 101059 100450 99903 100063 98701 98155 98340 96847 97406 96343 95683 96051 95665 95507 94736 94519 94032 92992 92967 92777 91518 91691 91135 90730 91122 90310 89807 89580 89365 89095 88735 88071 87570 86671 86192 85011 84374 83676 83483 82987 82819 82172 81842 81506 81246 80908 80424 80434 79096 78106 77924 77159 75955 75870 74821 74509 74493 73089 72385 71696 71621 71088 70946 70202 69697 69396 68411 68210 67832 67442 66908 66302 66205 65441 64972 64582 64136 63432 63088 62786 62403 61824 61560 60875 60592 59928 59785 59655 58645 58683 57964 57417 57363 57102 56679 55937 55672 55187 54888 54790 54341 53776 53633 52984 52699 52270 51868 51129 51097 50549 49829 50063 49837 49060 48436 48063 47846 47367 47329 46891 46324 46115 45591 45277 44851 44780 44023 43631 43369 43040 42763 42251 41899 41438 40906 40680 40150 39726 39667 39502 38848 38713 38154 38172 37571 36793 36780 36593 36236 35749 35300 35335 34530 34221 33719 33516 32891 32627 32508 31983 31541 30968 30809 30223 30289 29863 30075 29141 28857 28539 28001 27587 27453 26940 26813 26244 26251 25840 25175 24990 24895 24226 24082 23639 23492 22873 22801 22054 22129 21954 21508 21217 21021 20747 20148 19667 19896 19191 18948 18578 18168 17923 17773 17322 16787 17116 16572 16288 16022 15778 15643 15099 15059 14656 14505 13945 13738 13790 13185 13045 12971 12502 12274 12246 12111 11890 11647 11362 11158 10844 10751 10398 10277 10022 9777 9651 9428 9166 9124 8770 8710 8361 8358 8064 7972 7830 7516 7492 7273 7082 7023 6747 6581 6579 6415 6249 6107 5912 5890 5709 5640 5378 5220 5150 5156 4972 5009 4851 4728 4577 4490 4368 4246 4153 3937 4057 3833 3703 3686 3621 3541 3420 3288 3264 3126 3183 2982 2929 3002 2898 2738 2843 2572 2609 2547 2532 2455 2435 2244 2302 2168 2192 2070 1967 1995 1972 1870 1896 1810 1712 1717 1688 1605 1632 1551 1536 1502 1502 1385 1392 1317 1297 1251 1210 1256 1216 1167 1175 1135 1053 1090 1071 1003 1020 945 905 943 880 842 861 769 777 705 758 683 747 683 686 718 643 631 665 646 577 602 525 564 518 511 552 533 460 462 491 459 418 428 418 405 409 405 375 357 358 361 370 358 346 314 329 313 300 334 289 305 268 282 285 280 272 259 283 230 245 259 210 216 216 207 198 195 223 219 206 191 204 180 192 187 168 160 188 163 189 162 168 167 175 156 135 155 158 138 137 146 144 149 142 116 137 109 117 122 105 130 108 114 130 115 112 115 112 94 91 110 86 102 91 85 86 76 87 86 89 101 110 92 94 89 75 97 82 73 78 95 95 70 86 84 80 84 76 74 69 80 73 64 83 90 75 82 71 76 63 60 70 68 70 68 66 59 76 59 56 71 71 68 65 63 59 49 65 50 47 55 58 58 52 57 50 59 53 58 57 54 57 51 61 64 47 56 56 53 52 53 55 56 46 43 43 44 50 50 46 42 39 48 55 41 51 39 46 43 40 48 47 45 49 51 29 52 49 40 40 39 46 44 45 55 47 38 55 56 43 64 54 39 42 33 49 36 51 55 51 67 49 47 35 48 48 41 36 56 41 26 25 36 38 35 32 43 32 41 34 29 35 37 37 35 29 43 33 30 36 36 37 37 34 36 30 30 40 25 26 35 36 37 25 53 30 29 28 38 47 33 33 32 20 34 42 31 22 38 39 28 31 39 36 36 26 27 30 29 21 28 22 30 22 30 21 25 29 31 28 29 17 31 16 35 35 29 26 27 23 22 25 33 35 43 20 33 27 25 24 18 20 24 21 28 17 19 32 39 34 14 27 25 23 31 29 27 21 24 28 22 25 28 23 24 24 20 15 27 24 29 31 18 31 22 23 33 25 20 24 14 22 20 30 24 30 21 20 30 27 17 22 15 23 29 27 21 36 22 24 29 14 25 20 24 19 20 33 26 27 23 20 25 31 20 19 21 21 23 26 24 19 20 30 30 19 18 23 24 22 23 24 14 29 30 18 30 22 23 24 23 18 14 14 29 26 25 21 18 18 13 13 12 17 19 18 19 28 17 25 24 24 27 16 19 16 12 14 16 19 19 12 11 16 18 15 16 17 22 14 7 11 20 12 13 17 20 17 18 24 10 10 15 19 24 14 18 15 16 13 16 14 12 11 13 10 18 14 20 20 6 14 13 10 19 16 9 14 11 16 21 12 11 10 13 17 18 21 12 14 14 12 20 14 6 17 7 11 15 14 15 15 12 18 12 15 18 12 19 18 14 13 14 6 17 11 11 9 6 12 12 9 17 13 12 13 9 11 9 10 10 9 12 8 10 15 15 11 9 7 10 15 10 8 13 7 15 17 11 17 17 9 17 7 15 26 12 19 17 17 10 14 11 16 11 18 8 8 18 14 14 13 10 12 24 17 15 9 10 14 18 15 20 16 18 10 16 15 19 21 7 16 18 15 24 23 16 8 7 17 10 15 5 6 17 11 28 4 7 8 12 5 8 9 5 17 8 10 6 10 13 13 8 9 8 9 7 9 7 14 11 7 8 2 10 5 6 13 7 9 4 12 9 4 8 10 7 9 13 5 8 2 8 12 10 6 8 9 11 9 14 7 4 8 11 11 5 5 7 10 7 10 11 4 6 13 4 6 5 4 6 9 15 5 9 9 6 7 8 7 13 13 14 11 7 14 10 6 10 11 13 6 10 10 11 11 11 20 11 9 13 10 15 15 9 14 13 14 19 6 18 19 12 13 12 25 17 8 11 10 29 7 17 13 15 10 12 15 19 10 12 15 11 13 10 12 10 7 8 9 18 18 11 14 16 15 10 12 14 11 13 14 12 14 8 25 13 9 9 10 9 7 7 11 18 10 4 5 9 12 9 4 4 9 10 8 5 5 7 7 4 2 5 3 9 1 1 2 4 6 6 4 6 9 6 3 8 6 5 4 6 1 8 7 1 4 4 7 5 3 5 4 4 3 3 3 3 4 5 6 4 6 6 2 3 4 1 3 4 7 3 5 1 2 4 2 2 6 4 3 3 6 3 1 3 2 4 1 1 5 1 4 4 3 3 3 6 5 3 1 4 12 7 8 10 6 5 7 8 6 7 8 7 7 4 7 2 5 6 4 6 7 13 8 7 8 3 5 8 8 5 6 7 8 3 7 10 15 10 1 4 8 7 11 4 10 8 10 10 8 8 7 9 14 7 5 15 10 12 7 9 6 10 13 10 10 8 13 4 12 9 6 17 18 5 17 18 9 19 12 11 5 15 8 8 3 10 15 7 15 20 8 14 26 16 8 15 18 7 11 2 6 16 16 15 10 10 15 22 22 14 9 14 9 4 4 2 3 6 7 2 7 4 3 3 1 2 5 10 5 9 5 1 2 13 4 3 2 9 4 4 7 3 3 8 8 2 6 9 3 11 4 1 8 5 5 6 7 8 3 7 3 3 3 8 4 5 1 12 9 14 8 2 7 10 2 6 3 6 12 8 5 20 19 14 15 13 22 36 17 2 7 5 10 11 6 8 3 9 6 5 2 1 8 6 6 4 9 6 10 6 3 3 4 3 2 3 0 7 2 6 1 2 1 1 2 3 2 3 1 1 1 0 3 2 4 1 3 5 3 7 12 6 1 4 1 4 9 2 4 8 9 3 6 2 11 4 6 5 7 5 7 4 1 1 5 3 2 3 6 6 2 3 3 8 6 6 0 0 3 4 5 7 7 6 2 3 0 4 7 1 5 2 3 1 3 3 1 4 1 1 1 2 0 5 2 1 2 2 1 0 1 1 1 0 3 0 0 2 1 2 1 1 0 1 1 3 1 2 0 6 0 4 0 0 4 0 2 3 3 1 1 4 2 0 2 1 0 1 2 1 3 1 2 2 1 1 0 1 0 4 0 0 2 1 2 2 2 0 0 1 1 2 1 3 1 1 3 2 2 2 0 1 2 1 2 1 2 3 2 4 4 1 2 1 0 1 3 2 1 1 3 3 1 1 2 2 2 4 0 0 2 0 2 2 2 1 1 1 3 3 0 1 4 1 1 2 2 0 0 3 0 1 1 2 2 2 1 3 2 2 2 2 0 0 0 1 2 3 1 1 2 2 0 3 1 1 0 2 1 1 3 2 0 1 0 2 3 3 0 1 2 2 5 2 4 4 2 3 1 1 5 3 5 4 6 0 2 3 3 0 0 1 0 1 2 1 0 0 2 0 0 0 0 3 1 0 1 3 3 3 0 3 0 1 0 0 0 2 1 1 3 1 1 0 1 0 5 1 2 0 2 1 2 3 1 0 0 3 0 0 2 0 0 3 4 1 0 1 0 2 1 2 1 2 3 1 2 0 3 1 1 2 1 1 2 1 1 5 2 2 4 6 0 4 3 5 1 3 
];
B = [
0 0 0
 95695 60777 34918
 129009 85687 43322
 71188 46435 24753
 264050 187168 76882
 96704 68706 27998
 64355 46385 17970
 77143 56213 20930
 49224 36104 13120
 38325 28919 9406
 31119 23481 7638
 58443 43881 14562
 58993 43446 15547
 42164 30024 12140
 244385 185535 58850
 77483 57428 20055
 91828 70067 21761
 61244 46769 14475
 90399 69013 21386
 92708 70976 21732
 61255 47019 14236
 191877 148962 42915
 105378 81377 24001
 106448 82609 23839
 64872 50528 14344
 106058 82606 23452
 99753 78071 21682
 166182 129939 36243
 66448 51936 14512
 109739 85550 24189
 112405 88133 24272
 65891 51951 13940
 116000 91340 24660
 107648 84132 23516
 152692 120460 32232
 69501 55042 14459
 113756 89292 24464
 176130 141381 34749
 108556 85401 23155
 75986 61013 14973
 159738 128094 31644
 136468 107717 28751
 152013 121988 30025
 64143 51069 13074
 118868 94530 24338
 153884 123614 30270
 73169 58849 14320
 151600 121504 30096
 124177 98502 25675
 148301 119197 29104
 72386 58223 14163
 148491 119195 29296
 120851 96040 24811
 148937 119663 29274
 64801 52477 12324
 159081 128027 31054
 141203 113828 27375
 60364 48655 11709
 142633 114490 28143
 99382 78364 21018
 14892582 12394511 2498071
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1 17 0 0
1 1 0 0
1 1 0 0
2 0 0 0
3 4 0 0
4 4 0 0
11 6 0 0
26 6 1 1
131 6 1 0
474 9 4 0
887 14 92 12
1716 21 150 42
2803 34 236 98
4483 61 297 164
7934 121 479 290
18240 269 652 530
78229 520 1034 911
469853 1046 1684 1586
1224595 1881 3087 3080
648019 2901 5270 5173
85098 4288 7941 8073
14619 6091 10918 10633
14353 8655 13391 13605
16860 12447 16218 16407
19386 16651 19498 19217
22918 20974 22978 22824
26647 25499 26208 26328
30785 30759 30700 31029
34472 35110 35108 35015
39352 39961 38964 39514
42767 44137 43969 43531
47507 47829 47527 47359
50579 51905 50655 51169
54433 55212 54704 55303
58314 58657 57602 58266
60258 61310 60093 60865
63234 63987 63598 63568
65561 66327 65724 66088
68744 68960 68804 68703
71222 71748 71477 71112
74051 74654 74292 74828
77113 78019 77463 77264
80562 81219 81117 81068
84984 84663 84682 84535
88370 89527 88984 89486
93291 93688 93670 93470
97568 98297 97530 97231
101861 101794 101603 102313
104914 105659 104617 105429
106633 107521 106955 107291
107541 107472 108047 107528
106562 106679 106797 106697
103690 104225 103748 104155
99654 99981 99603 100215
94249 95598 94452 94617
88180 88122 87924 88080
80760 82137 81962 81406
74742 74436 74679 74542
68131 67803 68103 68448
62407 62558 62630 62487
58044 58262 57926 58419
55303 55417 55881 55834
53473 53934 53743 54095
53221 53529 53152 53454
54767 54566 53833 54350
56768 56825 56458 56810
59918 60605 60484 59926
66940 67203 65003 65629
70087 70680 69764 70189
74034 73738 73826 73990
76212 76120 75956 75927
76792 76522 76336 76677
72182 72053 71984 72241
63025 63164 62604 63002
53686 53156 53079 52802
42865 42922 42651 42684
32080 32175 32049 32041
22537 22520 22271 22644
16559 16849 16818 16892
11675 11842 11813 11932
7926 7975 7954 7873
5110 5226 5144 5043
447 470 475 457
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
