A = [
238557 218217 1350520 128094 104498 95981 85399 82559 82368 88815 108565 138323 167298 188399 209822 227204 230351 233416 240547 231175 227468 233956 231908 225683 224861 234778 226398 212837 216084 178727 173262 161142 115798 114981 113547 114025 112375 110867 112463 114153 113981 113108 114173 114674 112439 111397 111448 112506 109435 111215 112746 109950 112901 112086 110762 110264 109366 109215 107841 104393 105112 105136 104380 103712 102944 102034 100290 104296 105947 104698 110321 113835 115906 116223 117957 117491 117051 116849 115020 114777 112387 112515 112212 111659 110789 108780 106812 104007 102159 101437 101207 99828 99604 99387 98472 98046 96395 95903 93767 93200 92918 92368 91504 92150 91363 90270 89364 88776 87450 86386 85538 85013 84894 84881 83776 83016 83189 82093 81471 80348 80088 78896 78473 77794 77390 77077 76663 75648 74836 73942 73390 72240 71478 71296 71308 70783 70446 70079 68595 67708 66607 66623 65809 64921 64198 63900 64110 63199 62206 61469 60825 59767 59404 59354 57854 57754 56977 56729 56572 55528 54989 53850 53493 52530 52367 52056 51153 50731 50382 50019 48922 48622 47787 47224 46190 46126 45452 45235 44730 44122 43647 43012 42460 41871 41441 41024 40556 39696 39629 38974 38434 38014 37529 36716 36030 35596 35451 35081 34526 33886 33683 33127 32459 31854 31569 30948 30852 30276 29987 29258 28804 28667 28273 27530 27060 26976 26325 26070 25321 25293 24912 24536 24178 23385 22441 23032 21926 21589 21237 20900 20572 20178 19461 19244 19242 18422 17926 17926 17568 16965 16917 16520 16236 15898 15429 15214 14901 14846 14525 14021 13879 13749 13242 13030 12484 12309 12227 12145 11782 11427 10951 10997 10601 10608 10289 9822 9813 9570 9520 9179 9036 8981 8715 8453 8239 8128 7719 7577 7514 7291 7287 7178 6949 6624 6657 6612 6283 6260 6029 5870 5703 5551 5512 5394 5160 5049 4980 4838 4808 4615 4498 4436 4223 4230 4054 3856 3878 3850 3781 3615 3533 3409 3402 3238 3347 3166 3085 3021 2969 2854 2785 2709 2624 2484 2561 2486 2350 2313 2306 2199 2186 2098 2078 1994 1980 1974 1837 1855 1753 1675 1706 1598 1620 1544 1539 1535 1554 1532 1450 1355 1399 1426 1277 1350 1204 1312 1178 1218 1216 1104 1139 1085 1030 1059 991 943 953 941 892 926 870 796 804 825 753 772 676 752 662 661 698 646 699 629 699 624 612 597 572 621 570 547 556 539 470 538 457 448 474 422 341 411 352 394 385 352 369 363 341 311 315 316 284 286 290 261 265 255 225 252 226 266 240 247 228 196 218 190 198 187 197 212 194 211 194 194 204 161 163 141 158 192 153 146 218 172 149 144 188 158 140 148 126 132 118 127 136 121 136 106 119 108 159 124 127 118 142 132 122 125 141 117 118 93 84 114 104 99 104 97 100 98 97 70 91 80 92 78 86 82 98 72 96 82 80 78 82 72 61 89 77 76 71 66 50 76 58 90 66 64 53 74 63 58 53 58 60 69 73 58 59 65 44 62 56 67 47 52 56 62 59 54 48 69 42 60 42 48 49 53 54 55 48 39 39 76 33 49 47 53 39 36 49 57 23 44 49 33 56 38 64 38 43 53 55 51 65 74 62 58 57 58 60 62 62 58 64 57 66 78 64 64 55 46 42 62 61 48 56 43 79 65 41 74 63 39 57 44 57 65 41 58 68 67 45 52 69 74 52 63 53 56 51 52 49 36 69 63 36 63 41 54 42 38 37 30 31 33 32 28 38 34 77 43 37 52 48 44 35 52 50 31 48 26 36 20 30 41 34 29 32 29 30 30 20 23 24 15 23 27 40 25 18 25 23 28 14 25 31 20 27 24 31 25 29 29 27 29 24 19 26 21 18 34 18 19 23 19 13 18 20 27 20 18 27 23 25 18 19 15 25 27 12 22 26 11 27 31 22 22 21 23 23 16 21 19 24 18 19 19 20 19 21 22 13 17 25 21 16 18 22 20 29 38 78 42 17 37 37 28 41 28 21 39 39 24 35 28 24 30 27 26 19 23 35 29 24 31 17 24 14 19 18 15 16 17 21 30 22 16 27 15 23 31 28 21 11 20 26 20 25 14 19 12 15 23 16 15 13 21 17 19 19 19 18 18 19 30 23 13 13 12 20 17 22 21 23 24 28 31 22 17 21 28 13 20 20 21 20 17 16 22 13 11 15 12 10 19 14 17 14 12 14 13 10 14 13 16 13 15 18 13 16 14 13 8 11 13 8 13 14 15 9 12 15 17 13 18 22 9 14 19 13 10 18 12 6 13 12 15 19 13 7 15 12 11 15 14 12 8 7 9 8 15 16 11 19 9 11 13 8 13 11 15 11 5 15 8 13 3 14 13 13 17 22 14 17 6 14 7 11 15 10 16 14 8 10 8 6 12 15 11 14 9 10 12 11 16 8 8 7 16 10 15 12 7 10 11 11 7 8 15 13 9 9 9 6 11 8 10 9 20 13 14 12 19 27 7 7 14 7 10 8 10 10 9 4 12 7 11 9 9 13 8 12 4 11 9 13 14 7 9 9 15 7 8 7 15 3 16 9 8 9 4 8 11 10 10 7 18 10 11 9 10 12 18 11 6 10 8 7 14 14 8 6 2 11 6 8 9 9 11 8 3 6 6 10 6 8 9 8 10 8 7 5 12 13 13 8 8 6 7 5 15 9 4 10 6 13 13 11 3 12 5 9 9 11 10 11 11 10 9 11 7 8 6 12 10 4 6 5 3 8 6 2 6 8 9 4 8 8 4 8 6 10 3 3 9 2 7 3 7 6 6 5 10 6 6 7 7 6 8 10 4 9 6 15 12 12 17 9 13 7 11 15 10 27 16 12 15 23 25 11 8 18 14 21 14 7 12 31 29 22 20 12 24 31 16 22 13 17 27 11 19 22 24 20 7 5 8 3 9 5 5 8 4 3 87 13 6 8 10 6 10 7 5 5 2 4 4 5 5 14 11 7 7 1 5 4 2 5 2 4 7 6 3 5 9 7 3 2 2 5 3 7 4 4 7 2 8 5 7 6 6 5 5 5 5 3 4 3 4 4 4 9 6 10 6 3 5 4 4 5 2 2 9 5 4 3 4 1 6 7 9 4 7 3 6 4 2 7 6 1 5 11 11 2 2 14 20 16 16 5 11 20 14 9 12 12 12 23 15 4 14 21 22 11 9 20 22 24 20 13 14 15 21 24 13 14 15 23 14 17 17 28 11 14 14 26 17 29 10 9 18 18 25 11 12 16 13 29 11 13 12 18 24 4 10 13 23 20 14 7 8 27 19 15 12 7 6 24 5 10 5 5 20 6 8 7 12 16 10 9 2 5 9 5 1 2 4 1 0 3 4 2 0 2 3 1 2 2 2 7 4 2 1 5 2 2 2 1 2 3 1 7 3 3 2 1 4 0 1 2 7 3 1 4 2 7 3 0 6 2 5 3 1 1 2 3 4 3 1 5 3 3 6 5 5 6 1 1 3 1 5 1 2 2 8 5 4 2 3 5 0 0 0 1 2 1 3 1 2 0 1 1 1 1 3 1 6 5 5 4 1 0 3 1 0 1 2 1 0 1 4 2 4 2 0 1 5 3 2 1 3 0 0 1 2 2 0 1 1 1 1 2 2 0 0 1 6 4 2 0 3 1 6 1 1 5 1 2 1 0 0 2 2 2 2 3 0 3 2 1 1 3 4 0 4 0 1 2 5 0 3 0 1 1 2 1 0 5 1 0 1 1 3 1 0 0 1 2 3 5 3 7 13 4 15 14 15 16 18 18 29 16 3 11 17 15 13 9 13 12 4 15 10 15 20 17 26 2 19 11 24 16 11 17 12 19 6 5 15 9 19 19 7 15 9 11 12 12 15 18 34 19 3 7 15 9 12 13 17 16 13 10 8 13 7 13 14 2 25 16 5 15 7 12 7 8 11 10 7 13 15 17 2 12 11 7 13 12 8 14 9 18 24 16 14 15 14 0 10 8 2 10 9 2 11 10 12 3 6 8 2 0 3 1 1 0 4 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 2 2 3 1 1 4 5 2 0 0 2 4 2 0 3 4 2 2 2 0 4 0 1 3 2 2 2 3 0 5 2 2 1 1 0 1 3 1 0 2 2 3 2 2 2 2 1 9 4 3 1 4 5 2 5 5 1 1 0 0 0 1 1 1 0 0 0 0 2 1 1 1 2 1 1 0 0 1 0 1 2 0 0 1 2 2 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 2 0 0 0 0 0 1 3 1 1 2 0 0 1 0 0 0 1 0 1 0 2 1 1 0 0 0 2 1 1 0 0 0 0 0 0 0 3 0 0 1 2 1 1 0 0 0 0 0 0 3 0 4 1 0 0 0 1 2 0 1 0 3 2 0 3 0 2 1 0 0 1 1 1 2 1 2 2 1 0 3 0 1 0 0 0 0 0 1 0 1 2 0 0 0 0 0 0 0 0 2 0 1 0 1 0 2 0 0 0 0 0 0 1 0 0 0 2 1 0 0 0 0 1 0 0 0 0 0 0 1 1 3 0 0 0 0 2 1 1 0 0 0 2 0 0 0 2 0 1 1 0 2 0 0 0 0 3 0 0 1 0 1 0 1 0 0 1 1 0 1 1 3 0 1 2 1 1 0 0 1 0 1 1 0 1 0 0 2 1 1 0 1 2 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 2 0 1 1 0 0 1 0 0 0 0 2 0 2 0 1 1 2 2 1 0 0 0 1 
];
B = [
0 0 0
 58637 42373 16264
 80322 60769 19553
 61250 47006 14244
 145142 114136 31006
 80953 65613 15340
 57465 47008 10457
 55891 45365 10526
 41697 33798 7899
 33718 27664 6054
 22119 17753 4366
 28891 23331 5560
 30866 25326 5540
 25907 21554 4353
 97147 80053 17094
 44779 37749 7030
 54026 46251 7775
 46302 40056 6246
 53145 45096 8049
 54308 45734 8574
 42504 35887 6617
 91528 76596 14932
 60741 51127 9614
 62229 52821 9408
 46391 39736 6655
 63225 53868 9357
 59369 50869 8500
 83182 70364 12818
 47313 40151 7162
 64019 54348 9671
 65613 55896 9717
 48158 41293 6865
 68043 58200 9843
 62630 53407 9223
 83760 71351 12409
 49434 42617 6817
 65321 55715 9606
 115604 98699 16905
 62566 53679 8887
 57016 48975 8041
 104260 88846 15414
 77466 66495 10971
 98765 84552 14213
 46204 39942 6262
 72167 62174 9993
 99936 85428 14508
 55319 47801 7518
 98232 83925 14307
 71349 61181 10168
 97751 83525 14226
 53579 46372 7207
 95428 81778 13650
 73312 62647 10665
 96510 82238 14272
 50124 43591 6533
 102679 87718 14961
 88815 76095 12720
 46017 39531 6486
 90277 76917 13360
 56502 48483 8019
 7818961 6912570 906391
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 23 0 0
0 2 0 0
3 11 0 0
3 9 1 0
2 4 0 0
5 7 1 0
116 14 1 4
1901 11 2 1
21924 14 2 1
77800 37 1 3
127528 25 203 40
201381 39 342 102
289657 50 391 177
426854 126 472 272
668223 150 572 414
883548 340 709 603
823135 512 1158 1101
458934 768 1885 1784
131093 1328 2878 2817
24334 1886 4111 3972
7269 2763 5238 5118
6830 4044 6444 6348
8373 5928 7551 7600
9002 8006 9143 9001
10517 10127 10520 10766
12409 12349 12646 12614
14010 14452 14630 14498
16367 17220 16457 16671
18864 19164 18994 18642
20667 21499 20889 21381
23459 23356 22678 22951
25378 25582 25066 25206
27289 28040 26424 26890
29088 29639 29262 28655
35396 33297 30598 29707
30999 30851 30442 30491
30682 31609 30982 31363
31589 31894 31601 31551
32221 32278 32449 32521
32797 32563 32526 34016
33163 33465 33280 33094
34101 33997 33849 34246
35099 35508 34886 35007
36183 36624 36645 36474
37690 37637 37983 38063
39312 39087 39099 39238
41098 40911 40558 41171
42357 41816 42095 42600
43360 43630 43264 43674
44061 43715 44183 44025
43799 43679 43090 43754
42204 42666 42483 42726
40875 41181 40907 41030
38757 39152 38846 38758
35885 36560 35781 36470
32908 33408 32912 33244
30022 29970 30120 29901
27252 27417 26801 27110
24361 24826 24641 24623
22073 22452 22618 22452
20840 20792 20741 20899
19298 19771 19713 19848
18574 18815 18851 18921
18890 18718 18703 18760
18969 19187 19333 19204
20159 20152 20121 19972
21324 21122 21299 21736
32022 30191 27438 26002
25391 25011 25136 25097
26556 26496 26449 26674
26507 26573 26616 26545
26191 26063 25970 26228
23860 23804 24028 23741
20164 19760 20097 19952
16318 16270 16197 16144
12650 12608 12701 12849
9452 9471 9211 9484
6561 6800 6631 6581
5227 5116 5164 5159
3686 3723 3745 3591
2506 2613 2482 2612
1656 1559 1629 1617
140 146 155 137
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
