A = [
243488 236960 1376484 120137 104293 96057 82590 78650 75694 78045 88804 102230 118680 135331 149613 161572 164037 167941 170863 163134 159332 160390 157156 154263 155706 168829 168073 162516 169343 144728 142642 135522 104598 104102 105334 104546 104096 103234 102565 103353 103091 102805 104604 105292 105566 104535 104394 104489 103043 103062 104450 102624 104804 106949 105323 105017 103911 103413 101271 99055 99569 99758 98950 98838 99113 98882 96645 97828 99076 98014 100877 103546 104459 105847 107303 108455 108443 108117 107068 106102 105270 104471 103188 103074 103085 102273 101115 98828 97376 96563 95664 94716 94203 94026 94459 93576 93035 93149 92456 91277 90346 89749 89148 89063 89216 88748 89068 88117 87720 86701 85613 85795 85419 85100 84413 84485 84484 84202 83530 83118 82838 82209 81157 80981 80892 79566 80537 80368 79057 78355 78526 77628 77132 75902 75667 75857 75370 75065 74356 73924 73902 73296 72710 72006 70989 70863 70332 70182 70357 69768 69138 68760 67735 67382 67068 66060 65531 65422 65321 64511 64441 63800 63242 62215 61761 61532 60864 60877 60165 60176 59094 59243 57998 58162 57296 56407 56635 56191 55284 55029 54698 54290 53942 52970 52431 52406 51290 51575 51105 50942 50134 49646 49443 49007 48281 47787 47283 46972 46374 45783 45833 45263 44605 44213 43957 43355 43058 42748 42155 41483 40781 40373 40187 39445 39250 38815 38599 37942 37440 36878 36250 36090 35621 34615 34449 34696 33713 33123 32192 31851 31544 31207 30570 30264 30027 29145 28840 28637 27878 27477 27022 26553 26111 25666 26049 25294 24668 24496 23752 23755 23542 23277 22684 22248 22090 21650 21136 20856 20614 20012 19685 19599 19169 18770 18678 18161 17915 17692 17394 17097 16776 16404 16194 15757 15749 15257 15314 14780 14414 14111 14255 13924 13451 13290 13250 13027 12715 12467 12359 12102 11761 11603 11514 11245 10915 10953 10889 10362 10126 9991 9756 9764 9351 9413 9014 9143 8964 8693 8480 8328 8198 7899 7820 7872 7626 7431 7415 7221 6951 6764 6841 6619 6644 6482 6146 6145 5995 5919 5854 5714 5521 5529 5412 5319 5228 4962 4966 4919 4899 4785 4588 4531 4547 4352 4570 4294 4202 4059 4144 4026 4013 3854 3791 3748 3784 3612 3546 3515 3334 3385 3297 3110 3057 3005 3053 2943 2863 2852 2935 2738 2715 2599 2478 2542 2410 2452 2363 2318 2290 2242 2239 2134 2075 2079 2011 2016 1989 1878 1959 1910 1800 1817 1767 1803 1767 1669 1603 1585 1595 1527 1496 1448 1450 1383 1439 1385 1348 1360 1287 1216 1265 1294 1197 1178 1100 1114 1033 1030 1066 1029 969 998 984 983 898 901 917 838 862 885 832 853 782 762 761 730 764 712 697 723 703 659 686 651 667 634 611 640 598 575 552 604 567 530 515 514 535 498 516 489 478 487 446 417 462 463 426 392 416 422 456 416 405 389 384 387 337 390 329 387 344 330 352 333 342 333 301 317 337 288 290 267 298 273 294 273 278 275 267 235 252 260 256 256 216 240 205 226 198 195 206 198 174 213 206 191 180 201 146 159 183 169 178 175 178 147 161 161 159 134 152 153 167 158 149 136 125 135 120 138 120 133 110 121 133 163 109 121 118 132 106 125 105 138 93 115 112 114 99 107 99 95 85 88 99 92 102 100 147 98 92 97 106 97 97 93 102 99 109 82 96 100 98 77 81 81 83 102 87 83 86 75 85 104 103 78 84 94 83 74 91 80 73 97 82 77 83 93 76 89 74 80 89 60 75 66 59 56 51 86 70 52 63 61 46 45 53 46 53 55 56 55 87 65 58 51 57 52 65 56 65 52 59 47 36 44 40 49 40 27 41 44 36 38 43 41 44 35 51 43 31 34 33 33 41 33 30 35 35 40 33 35 28 39 29 39 42 33 39 29 37 23 32 36 37 41 36 33 37 36 36 31 43 32 23 35 22 25 29 30 27 26 31 26 33 21 21 24 27 21 26 32 29 26 26 38 22 24 23 31 26 33 35 33 20 13 29 28 22 15 30 19 36 32 70 37 29 46 42 47 40 48 39 36 29 38 35 30 28 42 41 40 28 28 25 38 36 28 23 26 17 23 23 24 23 15 20 28 16 20 24 17 22 35 33 22 25 25 21 20 23 18 21 26 29 21 24 16 19 26 18 19 27 22 32 20 23 29 25 30 17 23 15 23 21 24 24 31 21 25 29 27 26 17 22 22 26 12 20 23 24 14 12 16 23 13 13 18 13 17 12 19 20 16 16 17 21 23 12 18 21 19 12 25 21 17 18 8 9 11 14 14 20 17 15 23 16 21 25 15 15 17 20 13 5 9 6 9 16 20 26 13 12 16 14 13 19 19 13 17 18 12 20 20 14 14 14 13 12 13 16 18 24 5 20 19 13 12 14 17 10 12 19 18 13 30 18 18 12 22 18 26 14 15 11 11 11 13 7 14 13 15 13 17 18 9 16 9 11 20 14 10 7 15 12 13 17 13 16 12 12 8 14 5 17 6 13 6 3 23 14 11 18 15 18 15 19 19 9 12 15 9 16 15 12 9 11 9 9 7 10 10 15 10 12 6 12 16 8 13 15 7 8 10 10 8 12 10 7 9 9 4 17 18 12 9 13 5 9 11 5 15 14 9 8 17 17 3 9 9 8 13 12 11 7 9 8 10 13 10 9 8 13 8 9 8 7 12 11 9 7 10 19 10 12 11 13 19 16 9 16 11 7 13 4 7 6 9 11 11 10 7 9 14 11 15 16 10 7 11 11 8 10 9 8 5 6 11 6 4 7 6 8 2 4 6 10 13 5 2 3 5 7 6 5 5 6 8 5 6 6 13 8 8 5 9 11 10 4 7 7 9 3 14 9 2 10 13 8 12 11 8 14 9 13 10 19 12 11 13 16 19 12 6 17 10 16 11 7 14 24 17 16 17 20 17 18 12 11 20 17 17 13 11 25 10 12 5 9 5 2 7 8 3 7 4 6 78 11 9 8 11 9 8 5 6 10 7 7 3 5 10 7 2 2 5 4 6 6 5 2 6 6 2 3 8 7 2 4 3 5 9 6 3 5 6 7 3 4 4 6 6 4 5 5 5 6 5 4 10 6 4 6 7 9 5 6 3 7 6 6 7 4 4 7 6 3 3 4 9 8 5 4 6 4 3 7 3 2 2 4 12 2 4 11 9 3 2 8 15 10 12 7 10 8 13 7 5 13 13 6 7 8 10 17 17 6 8 11 6 22 20 10 19 14 26 12 21 15 3 14 8 17 9 16 16 14 11 14 20 15 11 8 10 5 15 10 9 14 12 19 6 8 9 9 15 7 12 13 14 16 8 15 3 12 16 6 5 7 8 15 6 5 2 7 9 7 3 1 4 20 9 8 4 1 4 5 3 5 4 1 0 2 0 4 3 6 6 3 4 2 3 4 7 1 1 3 2 3 8 3 2 2 4 2 4 4 2 2 3 5 1 4 4 2 6 2 6 3 4 1 5 3 5 2 3 3 3 5 5 2 0 1 4 4 4 6 6 4 4 3 4 4 1 2 2 1 1 5 3 2 4 2 1 1 1 3 2 4 4 2 1 2 3 1 2 2 1 3 5 6 1 4 3 2 2 2 1 2 2 2 2 1 4 4 6 2 3 1 2 4 1 2 2 1 2 0 3 2 0 2 2 2 0 0 1 1 3 4 1 2 0 4 3 2 5 0 3 1 2 3 3 1 2 2 4 0 2 4 3 5 1 3 1 2 0 2 3 1 2 2 0 0 0 0 1 1 4 4 6 2 1 3 2 2 1 3 1 1 2 1 0 2 5 2 4 7 6 14 6 12 8 9 16 14 6 4 7 4 4 11 8 5 6 12 4 16 5 16 18 8 10 17 9 15 16 13 6 15 13 4 8 10 14 11 6 15 8 11 14 9 12 14 23 8 4 15 15 11 7 6 10 6 16 9 8 9 13 17 7 6 13 12 5 9 8 8 12 5 9 14 7 12 12 15 6 3 13 10 14 12 12 12 7 15 4 9 16 20 13 1 4 10 7 5 10 0 6 5 3 3 9 6 3 0 2 2 0 0 1 0 3 1 2 1 4 0 1 1 0 0 0 1 2 2 0 4 0 1 1 0 3 1 2 1 1 2 5 2 3 3 4 1 1 2 3 2 0 0 3 3 1 1 1 2 2 1 0 3 2 2 4 1 4 1 2 1 2 3 3 2 1 1 2 4 7 4 5 3 4 6 1 1 3 0 0 0 2 3 1 1 0 0 1 1 0 1 2 1 0 1 3 0 0 0 1 0 0 2 0 0 1 0 0 0 0 0 1 0 1 3 0 0 0 2 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 2 2 1 0 2 1 0 1 0 1 1 1 1 1 0 1 1 3 0 2 0 3 3 1 1 1 3 2 2 1 0 3 3 1 2 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 6 0 1 1 3 0 0 0 3 0 1 0 1 1 0 0 0 0 0 0 0 1 1 3 0 0 0 0 1 1 0 1 3 1 1 3 0 0 1 2 0 1 0 0 0 3 0 0 0 0 2 0 0 1 0 0 0 0 1 2 0 0 0 1 2 0 2 0 3 0 1 0 2 0 1 0 0 0 1 0 4 1 1 0 1 1 0 1 0 0 0 0 1 1 0 0 4 2 0 1 1 1 1 1 1 0 0 1 0 1 2 4 0 0 1 1 0 1 0 0 1 2 0 0 0 0 2 0 0 0 0 2 0 1 0 3 1 0 0 0 1 0 1 0 1 1 1 2 0 0 0 0 0 0 0 0 2 0 4 0 4 2 2 3 0 0 
];
B = [
0 0 0
 52406 36439 15967
 74755 54251 20504
 50609 36985 13624
 147154 110758 36396
 69076 53663 15413
 46884 36975 9909
 50042 39426 10616
 35151 27811 7340
 28035 22420 5615
 18205 14341 3864
 28607 22562 6045
 30000 23638 6362
 22432 17950 4482
 111318 87799 23519
 42212 33864 8348
 49880 40765 9115
 38188 31843 6345
 49225 40051 9174
 50869 41083 9786
 36574 29837 6737
 97885 78811 19074
 58039 47318 10721
 58724 48010 10714
 40020 33221 6799
 59337 49018 10319
 55979 46115 9864
 84805 69060 15745
 41932 34476 7456
 61882 50725 11157
 62946 51645 11301
 42246 35341 6905
 65699 54359 11340
 60886 49807 11079
 82127 67414 14713
 43872 36736 7136
 64049 52548 11501
 104446 86945 17501
 60884 50136 10748
 49496 41530 7966
 94735 78862 15873
 76084 62692 13392
 90261 75378 14883
 41525 34722 6803
 69307 57506 11801
 91831 76808 15023
 48758 40916 7842
 90236 75118 15118
 69863 57876 11987
 90318 75033 15285
 47812 40228 7584
 88803 73949 14854
 71644 59133 12511
 90588 75199 15389
 43973 37009 6964
 96135 79670 16465
 84903 70539 14364
 40812 34191 6621
 86362 71320 15042
 57260 47002 10258
 8246276 7037890 1208386
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
2 50 0 1
1 5 1 0
0 14 0 0
4 11 1 0
1 10 0 0
5 7 2 1
13 18 2 2
154 17 9 5
1446 17 7 11
5301 35 12 13
10031 30 256 56
18289 43 405 122
33388 65 471 225
76321 132 573 342
214213 220 737 521
514775 371 888 723
749647 637 1217 1083
569372 978 2049 1885
249159 1586 3104 3063
77496 2207 4642 4644
21280 3236 6190 6132
9686 4800 7583 7387
9728 6769 9137 9122
10852 9016 10737 10734
12775 11736 12722 12612
15032 14413 14888 15108
17600 16997 17447 17469
20479 20211 20074 19991
22780 22927 22748 22804
25283 25512 25320 25703
28154 28068 28252 27932
30912 31070 30785 31149
33116 33163 32809 32966
35336 35478 35330 35208
39617 37897 37010 36286
38211 37618 37673 37393
38263 39056 37776 38573
38235 39125 38808 39340
39453 40013 39598 39973
39818 39813 40286 40457
40646 40976 40694 40581
42264 41930 41860 42143
43168 43476 43159 43317
44673 44873 44587 45193
46330 46730 46633 46758
48318 48670 48572 48767
50497 50357 50021 50852
51657 51769 52044 52119
53628 53301 53563 53429
54043 54030 54188 54231
53699 53556 54098 54419
52555 53139 52899 53221
50673 51243 50875 50728
47997 48160 48633 48508
45343 45536 44932 45041
41509 41649 41590 41381
37625 37852 37623 37825
33776 34359 33938 33986
30566 30706 30935 30618
27702 28049 28039 28267
25952 26180 25946 26033
24859 24560 24839 24883
23454 23851 23290 23537
23459 23473 23237 23281
23922 24160 23590 24124
25366 25242 25169 25524
26909 26987 26833 26716
36137 34697 32543 31743
31728 31450 31683 31513
33179 32978 32934 32944
32966 33592 33112 33283
32792 32604 32637 32772
29737 29759 30043 29946
24628 24945 24807 25160
20493 20650 20342 20490
15997 15924 15689 15662
11771 11963 11687 11621
8369 8122 8251 8420
6219 6405 6255 6141
4520 4581 4715 4612
3103 3069 3056 3104
1896 2017 1853 1926
147 174 148 156
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
