A = [
74891 69667 178478 76033 72113 66578 66527 66712 72774 72953 89662 89331 100619 125134 152946 182845 196582 200808 199604 199530 179495 158283 147077 140802 139946 157664 156261 153342 156321 132414 131421 120297 91952 92855 89331 91889 91183 83003 85271 83735 80471 83808 82185 83827 87884 87655 85322 83168 86945 83573 80127 79222 82407 82335 82843 85489 80913 84455 83690 77679 76434 78470 77659 76600 78012 81236 80351 79179 79093 78644 76453 77069 77915 77890 78971 80364 81489 79645 79069 77729 75870 75295 72637 72718 73613 73568 72118 70630 70264 68817 68171 67440 67181 66978 67211 67533 66111 66480 66763 64533 63963 63687 62621 62629 62378 63153 62714 63127 62380 61903 60921 60531 60196 59750 59782 60006 60365 60339 60158 59356 58847 58123 57672 57198 57554 56778 56960 57890 57330 56577 56162 55628 55197 55590 54166 54460 53946 53644 53229 53108 53360 52963 52751 51795 51694 51569 51143 51275 51468 51842 51484 50940 50544 50143 49281 48516 48754 48232 47809 47907 47570 47219 46715 46514 46249 46166 46398 45699 45358 45732 45413 44844 44912 44721 43934 43705 44188 43442 43275 42905 42640 42428 42479 42627 42284 41982 41996 41402 40931 41705 40593 40787 40635 40177 39811 39775 40262 39516 39605 39481 39505 38824 38553 38382 38461 38305 38170 37855 37974 37246 36967 36350 35774 36092 35898 35184 35352 34553 34517 34407 34526 33975 34013 34312 33708 33809 32982 32746 32502 32249 32167 31983 31958 31454 30935 31048 30846 30463 30062 29803 29282 29824 29832 29190 29297 28824 28663 28469 28885 28310 27837 27984 27872 27608 27692 27021 26359 26920 26561 26379 26211 25903 25982 25751 25723 25070 25161 25092 24966 24428 24354 24301 24342 23885 23806 23711 23423 23470 23730 23130 22867 22909 22720 22653 22672 22366 22223 22007 21609 22050 21693 21908 21608 21422 21091 21186 21093 21056 20702 20599 20279 20368 19901 19924 20065 19853 19651 19588 19292 19317 18882 18781 18590 18554 18552 18144 18065 18196 18137 17996 17654 17577 17299 17374 17407 17072 16821 17106 16390 16533 16499 16547 16193 15923 16060 15592 15763 15456 15902 15429 15131 15210 14633 14548 14300 14309 14507 13999 13775 13539 13556 13335 13255 13041 12604 12454 12541 12310 12114 12210 12004 11696 11164 11131 11051 10888 10519 10597 10438 10215 9937 9627 9540 9089 9151 8979 8774 8407 8318 8228 7745 7864 7455 7580 7395 7048 7136 6724 6661 6633 6397 6289 5983 6113 5866 5404 5551 5224 5013 4960 4789 4730 4619 4385 4445 4304 4103 3852 3791 3844 3677 3461 3310 3278 3046 2993 2877 2663 2758 2690 2590 2444 2477 2322 2202 2115 2026 2084 1991 1838 1812 1778 1648 1668 1628 1471 1469 1449 1371 1371 1274 1215 1254 1192 1053 1043 1062 970 969 923 851 883 874 740 747 731 751 698 644 704 613 578 631 579 558 482 531 484 480 425 421 429 405 383 365 335 347 360 336 329 299 298 340 287 263 239 239 224 272 229 232 240 221 254 233 228 244 273 161 178 164 191 163 148 196 147 136 207 127 121 127 93 74 102 100 93 83 67 98 82 85 81 96 72 63 72 57 67 69 61 61 62 47 61 60 75 69 51 62 50 50 48 37 53 56 45 35 53 40 54 61 47 39 39 48 40 33 35 34 43 49 39 37 45 42 96 114 44 91 66 33 54 45 34 45 31 42 81 137 80 60 57 35 70 48 44 42 24 124 63 30 82 81 41 52 41 38 46 41 36 69 30 44 93 101 51 36 35 30 35 30 58 29 29 61 112 26 58 50 33 28 21 23 32 17 37 20 28 23 25 27 29 33 67 51 32 20 112 21 19 20 47 23 26 28 17 25 21 20 30 12 28 23 18 22 34 31 14 17 12 18 20 18 22 12 22 29 19 22 29 25 28 12 24 13 16 25 18 17 21 22 27 17 18 26 22 11 16 20 23 29 16 27 9 15 19 26 18 20 7 19 21 14 10 22 20 23 20 12 12 25 20 15 13 16 13 10 16 16 16 19 11 20 15 15 15 18 12 21 12 10 16 24 29 37 106 61 27 57 65 46 70 67 43 20 31 134 23 28 34 20 65 67 10 29 30 20 26 17 14 8 11 13 16 21 11 21 14 15 19 14 13 15 23 60 39 23 31 16 21 17 18 9 8 21 14 18 12 13 23 18 24 23 12 13 88 13 14 27 24 81 38 14 20 14 52 24 18 31 30 78 39 19 27 26 31 32 21 14 9 9 19 12 16 12 14 5 9 9 9 10 8 12 6 14 6 12 9 9 10 12 10 12 9 7 4 11 8 9 19 13 13 8 11 5 13 13 15 12 82 18 11 33 31 15 19 20 13 12 9 64 12 11 15 14 26 9 21 11 2 11 20 14 13 28 58 14 20 37 22 10 10 12 20 23 8 9 22 23 62 23 22 12 29 47 14 15 25 49 42 18 33 22 24 31 27 15 21 22 29 22 13 18 15 49 32 17 17 15 33 21 12 14 21 63 41 18 34 18 52 27 11 11 13 29 12 16 28 18 29 34 13 27 11 44 47 27 25 37 31 36 24 19 19 33 30 7 11 24 22 37 9 13 11 32 15 11 9 6 23 35 18 22 16 19 36 17 11 10 24 61 7 24 14 35 33 13 29 18 64 53 18 16 15 68 39 14 9 23 54 45 22 27 21 61 77 10 34 18 83 49 8 14 22 33 22 4 4 2 13 12 1 8 7 15 14 2 6 16 21 3 6 8 2 7 5 6 5 1 3 6 25 4 8 5 7 4 5 6 3 6 7 5 6 7 4 5 7 3 5 9 7 4 9 4 4 2 3 2 8 6 8 4 3 6 3 7 3 1 2 4 9 5 6 3 2 3 3 8 4 4 9 4 11 4 10 10 13 10 24 27 6 27 5 57 24 23 14 13 64 49 9 13 8 41 41 8 15 27 41 21 32 37 23 36 47 18 11 26 22 61 27 56 38 89 29 31 10 9 27 9 6 12 7 5 8 6 8 7 10 7 4 3 5 1 6 2 6 1 3 2 11 4 2 2 2 7 4 6 4 6 7 5 2 0 6 6 6 2 1 5 1 3 3 3 3 1 2 1 4 9 1 4 3 4 7 1 4 5 2 3 5 1 5 0 3 6 5 2 2 4 5 8 0 0 6 2 2 4 1 3 6 5 4 4 1 3 3 6 2 8 6 10 1 10 4 10 6 3 26 13 12 8 15 8 11 11 2 15 21 6 15 19 19 19 6 11 20 35 29 18 19 16 32 14 2 12 13 2 24 4 13 7 15 16 8 12 13 17 7 2 16 7 13 10 3 10 15 9 9 4 5 12 2 9 2 6 5 1 9 4 10 5 5 10 3 6 12 6 3 7 5 9 0 5 4 14 8 3 1 6 5 3 6 4 2 8 4 5 3 2 2 4 3 2 2 6 1 1 1 2 2 3 0 4 3 1 3 1 0 0 1 0 1 2 7 4 4 1 2 1 1 0 2 1 3 2 1 0 1 4 1 3 2 3 4 2 7 2 4 3 2 2 0 3 1 2 2 2 2 9 5 1 0 1 10 1 3 2 7 3 1 0 1 1 1 1 3 3 2 2 5 0 2 4 3 2 5 5 2 14 4 2 4 5 2 2 0 8 4 13 3 3 5 4 7 0 4 8 9 4 5 5 11 5 0 3 7 9 3 2 5 6 3 5 1 0 0 3 5 1 3 8 12 4 2 3 1 1 3 3 4 3 8 4 3 2 5 2 2 9 3 5 13 14 1 11 9 8 9 11 5 2 7 1 3 2 9 17 5 3 7 11 21 5 0 3 4 16 2 8 1 3 10 12 2 7 21 29 22 9 3 4 9 19 8 4 7 2 4 8 3 5 10 5 28 3 6 14 26 22 14 8 4 5 5 7 4 4 48 12 3 2 6 4 22 1 4 3 2 7 8 10 10 25 8 2 10 1 16 17 0 5 2 2 15 6 4 5 49 26 5 12 3 5 4 2 4 7 8 33 6 8 10 30 14 5 7 12 59 21 10 3 12 16 37 1 11 5 68 37 3 6 0 6 16 6 4 12 8 20 4 4 1 0 2 0 0 4 1 0 2 0 2 2 1 1 1 1 1 0 0 0 1 3 0 0 5 2 3 1 8 2 2 1 4 7 8 5 5 2 1 8 2 6 4 2 10 4 0 1 2 8 2 3 1 4 3 2 1 5 2 0 0 1 3 3 1 0 1 3 3 6 2 3 16 2 5 2 6 30 0 3 2 1 5 2 0 1 2 0 1 2 0 1 1 4 0 2 1 1 1 1 0 0 1 0 1 0 1 0 0 0 1 2 1 0 1 0 0 0 0 1 0 1 0 2 0 2 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 2 1 2 0 0 1 0 0 2 1 1 0 1 0 0 0 0 0 1 0 2 0 1 0 0 1 0 3 1 3 0 2 0 0 2 1 1 2 0 0 0 0 1 1 1 0 0 0 0 0 2 1 0 2 1 0 0 2 0 0 0 1 0 1 2 0 1 2 0 0 0 1 0 2 0 1 0 0 1 2 1 2 1 1 0 0 0 0 1 1 0 1 0 0 1 2 0 1 0 0 0 0 0 1 0 0 2 0 0 0 1 1 1 0 1 1 0 1 1 2 2 1 5 5 2 2 1 6 1 1 2 2 7 1 8 0 1 0 0 0 3 3 0 0 0 2 0 0 0 0 0 1 0 0 1 0 2 1 1 2 0 0 0 0 0 1 3 0 0 1 1 1 1 0 1 2 0 0 1 1 2 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 2 4 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 2 0 
];
B = [
0 0 0
 43251 33012 10239
 67274 54835 12439
 46257 37026 9231
 132506 108885 23621
 59181 48937 10244
 41010 34516 6494
 39182 32860 6322
 25359 20915 4444
 20644 17100 3544
 11176 9385 1791
 20527 17240 3287
 16647 13933 2714
 21123 17941 3182
 91152 78253 12899
 31126 26646 4480
 37882 33068 4814
 34580 30255 4325
 29249 25659 3590
 38050 33091 4959
 32052 27934 4118
 72560 62967 9593
 37917 33095 4822
 45390 39592 5798
 37973 33396 4577
 35509 31185 4324
 43620 38305 5315
 53002 46482 6520
 29002 25693 3309
 60391 52674 7717
 47612 41764 5848
 38586 33953 4633
 39610 34974 4636
 46740 41296 5444
 53562 47178 6384
 31942 28321 3621
 56263 49428 6835
 72028 63243 8785
 36633 32387 4246
 44505 39295 5210
 67455 59176 8279
 52880 46656 6224
 53596 47195 6401
 42973 37913 5060
 50739 44910 5829
 54553 48013 6540
 43043 38027 5016
 64831 57104 7727
 51091 45060 6031
 52874 46626 6248
 45052 39859 5193
 63671 56027 7644
 41613 36823 4790
 65950 58059 7891
 40022 35375 4647
 58915 51909 7006
 62978 55381 7597
 38101 33647 4454
 61124 53867 7257
 33502 29806 3696
 6762905 6083435 679470
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 7 0 0
0 0 0 0
1 1 0 0
1 1 0 0
1 3 0 0
6 1 0 0
5 2 0 0
13 5 0 0
66 9 0 1
113 11 1 1
267 10 29 11
474 22 78 26
801 27 84 60
1287 37 160 108
2290 102 269 225
5295 191 444 423
42789 370 788 785
565664 588 1360 1274
1340736 1256 2340 2368
264993 2243 3592 3641
11320 2891 4963 5087
7261 3863 6473 6306
8949 5507 7754 7892
9712 7349 9204 9306
11234 10096 10732 11423
13456 11849 12714 13143
15428 14249 14806 14904
17466 19874 16945 16798
19788 19895 18869 18978
21183 21902 21091 21223
24230 23237 23156 23537
25160 25097 24539 25233
26693 27005 25713 26342
28812 28244 27922 27929
30714 29034 28682 29185
32500 29796 29882 29118
32861 31131 32761 31974
30248 30706 30547 31092
31511 31276 31619 31423
31987 31778 32036 32125
33078 33300 32968 32884
34312 34263 33919 34004
35270 35658 35374 35490
36732 37011 36497 36891
38205 38434 38089 38184
39658 40210 40218 40215
41519 41915 41380 41554
42780 42767 42542 42566
43183 43937 43786 43701
44359 44277 44222 44655
44339 44160 43938 44153
43106 43435 43147 43272
41178 41472 41593 41766
39841 39421 39526 39702
37032 37569 37049 37473
34371 34358 34695 34165
31478 31378 31518 31791
28712 28787 28584 28162
25990 26227 25972 26032
23567 23890 23772 23578
22139 22433 22306 22113
21055 21061 21094 21230
19869 20146 20113 20205
19908 19849 19888 20179
20569 20126 20521 20119
21170 20839 21149 21155
22319 22337 22340 22213
38246 38357 28357 29082
25955 25627 25689 26161
26978 26951 27039 27396
27726 27901 27713 27920
27878 27981 27963 28161
26077 26150 26160 26015
22603 22374 22271 22675
18576 18632 18767 18795
14995 14840 14559 14630
10882 10949 10951 10908
7539 7371 7370 7590
5459 5481 5379 5584
3809 3859 3949 4000
2649 2504 2489 2654
1745 1762 1815 1790
184 210 179 200
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
