A = [
403166 360399 1583284 417757 372871 379501 366019 369303 365436 350177 348232 351142 344222 341070 342681 338583 334898 336216 330326 327587 327695 323518 320839 330242 349219 479929 485540 499205 627402 623573 614717 614137 615253 605601 602784 597058 582762 576125 569121 556872 552871 547937 538147 537167 529942 518669 514172 506364 494416 489855 484109 473643 470610 468213 457201 453417 448230 438812 433243 426503 418030 413077 408231 400037 397549 392386 383060 378657 374635 364415 359273 356776 349610 344322 340147 332427 330283 324934 316934 312567 308829 301752 297857 294966 287908 285926 281563 276166 271986 268168 261844 258326 254258 248749 246680 243351 237704 236346 231961 227137 224564 219033 215135 212764 209083 204032 201982 199529 196000 192874 190094 186379 183219 178594 175392 175165 171789 167169 164951 162670 159681 156812 154062 150600 149078 147147 144192 142550 139654 136815 134925 131866 129914 127106 125038 121940 121469 118754 115807 114995 113310 110111 108635 105808 104241 102768 100702 98937 97093 95905 93463 92270 90850 88356 87148 85353 84460 82654 81546 79830 78478 77203 75977 74640 73479 72274 71134 69965 68147 67413 66501 65801 63647 62272 60934 60474 59210 58079 57316 56216 54960 54011 53556 51597 51335 49908 49006 48068 47223 46254 45656 45162 44717 43643 42289 41914 41155 40525 39607 39228 38216 37368 36922 36549 35604 35060 34795 33509 33428 32843 32075 32160 30770 29981 29629 29250 28654 27833 27393 27073 26432 25913 25911 25448 24613 23993 23965 23186 22745 22288 21850 21416 21289 20841 20434 20109 19768 19547 19267 18809 18360 17892 17712 17727 17158 16671 16449 16091 16127 15694 15357 15106 14749 14619 14193 13975 13947 13425 13118 12964 12772 12742 12335 12024 12035 11886 11648 11220 11184 10887 10899 10627 10476 10088 10213 9962 9741 9422 9291 9324 9101 8585 8488 8527 8118 7917 7910 7942 7621 7652 7442 7167 7226 7173 6761 6677 6664 6380 6390 6185 6139 6030 5969 5754 5705 5555 5352 5410 5284 5224 5185 5023 4763 4777 4837 4520 4570 4423 4395 4327 4244 4255 4072 3930 3907 3891 3783 3675 3544 3574 3524 3337 3393 3424 3272 3231 3248 3172 3042 3176 2910 2864 2981 2777 2751 2656 2661 2648 2554 2614 2534 2519 2440 2355 2328 2313 2173 2272 2097 2110 2073 2129 2133 1896 1887 1837 1823 1829 1767 1787 1724 1741 1664 1637 1582 1676 1513 1479 1440 1518 1526 1414 1410 1379 1366 1339 1250 1204 1189 1206 1196 1196 1141 1135 1124 1135 1109 1061 1077 972 1045 1031 1012 964 927 989 1000 932 868 892 902 851 833 783 756 735 729 712 784 752 683 681 650 668 675 629 620 617 674 639 624 584 601 591 559 562 521 512 519 492 477 485 433 411 464 406 494 436 438 408 450 420 403 414 395 373 400 373 360 348 378 371 322 336 324 320 305 292 310 315 309 310 326 298 267 306 254 282 297 261 264 245 271 270 238 212 230 223 213 230 214 245 223 228 207 208 189 201 198 197 195 199 194 203 166 162 162 162 172 145 172 159 166 149 176 161 139 142 139 128 152 121 141 132 147 143 123 116 136 143 106 133 129 124 114 122 136 130 114 116 116 95 103 113 106 100 96 81 95 74 67 81 69 78 73 92 71 72 63 73 81 80 75 71 52 63 83 77 91 62 55 61 73 76 56 58 62 59 54 66 67 64 61 67 57 50 51 37 42 34 41 46 42 52 51 47 44 43 52 32 56 36 39 42 38 40 38 49 36 54 52 42 42 26 33 33 35 39 36 42 31 50 35 23 43 23 25 20 28 22 25 29 28 34 29 27 27 23 22 31 24 25 30 18 20 18 19 28 20 30 26 25 18 23 11 19 21 21 19 16 19 25 24 23 9 8 11 21 17 23 9 13 27 12 16 18 12 18 16 24 13 23 20 13 10 19 16 13 17 17 15 15 8 7 12 14 16 17 17 21 15 14 12 9 17 7 11 10 9 8 10 12 10 13 15 9 9 11 14 16 5 11 12 10 12 11 9 16 11 10 14 16 10 12 9 12 12 8 17 14 7 13 16 5 11 8 8 7 10 10 17 6 6 7 10 14 8 12 8 7 13 9 9 10 7 10 10 16 3 7 8 5 4 7 7 6 5 10 10 15 5 4 8 8 7 13 15 9 5 12 7 12 7 3 3 11 9 12 10 7 6 10 11 9 9 9 10 3 4 9 6 3 5 5 9 1 6 7 7 2 7 12 7 6 10 8 7 6 4 5 2 6 9 7 2 5 1 8 8 6 1 2 6 2 3 6 2 5 4 3 3 4 3 3 5 7 3 7 2 4 3 3 6 5 4 4 3 5 4 1 3 4 7 2 2 1 5 0 3 5 2 1 1 3 4 3 2 2 2 3 5 3 4 5 1 3 2 0 2 2 3 6 4 2 6 0 4 1 4 2 1 0 2 2 4 4 3 1 2 6 2 1 4 4 5 4 1 2 2 4 3 2 2 7 1 2 3 5 4 2 5 1 3 3 7 3 2 2 1 3 3 3 4 2 2 2 2 4 5 2 3 4 5 1 1 2 3 4 3 5 3 3 6 2 1 2 1 1 3 2 4 4 3 1 2 7 5 2 2 1 2 4 4 2 1 4 3 3 4 3 2 3 4 3 1 3 5 3 2 5 3 3 0 1 1 0 2 0 6 4 2 1 0 1 3 2 3 1 2 2 0 4 4 5 1 4 2 3 4 1 5 2 0 2 0 0 1 2 0 1 4 1 2 1 2 1 0 2 1 2 0 2 1 2 1 1 2 3 3 2 2 0 0 2 2 0 1 1 1 1 1 0 2 0 1 2 1 4 0 7 0 3 0 4 3 1 2 4 3 3 0 2 0 1 3 3 1 3 0 1 1 0 2 1 1 1 3 0 2 1 2 1 0 2 2 2 0 3 2 2 1 0 1 0 0 4 2 1 3 2 1 2 2 0 1 2 3 2 1 0 1 1 2 1 0 2 0 2 3 1 0 1 3 1 0 0 2 2 2 1 1 3 0 0 1 2 3 2 0 1 2 2 2 1 0 2 0 1 4 0 2 2 3 1 4 3 1 1 1 1 1 1 2 1 2 1 0 2 2 0 1 2 0 0 1 1 0 2 4 2 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 2 0 0 1 2 2 1 2 0 0 1 0 0 0 0 1 0 1 3 0 1 1 2 0 1 2 0 0 0 1 1 1 0 2 1 0 2 0 1 0 0 2 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 2 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 2 2 1 0 0 1 0 0 0 1 1 1 2 0 1 0 0 2 0 1 1 0 0 1 1 1 0 0 0 2 0 3 1 0 0 2 0 1 1 0 0 0 1 0 0 1 0 0 2 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 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 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 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 2 0 0 0 0 2 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 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 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 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 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 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 2 0 1 2 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 2 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 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 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 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 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 
];
B = [
0 0 0
 24478 9119 15359
 9965 3793 6172
 44009 21959 22050
 12560 4486 8074
 10915 4567 6348
 16940 5924 11016
 20193 9027 11166
 10010 4210 5800
 44532 22511 22021
 11651 4942 6709
 11320 5138 6182
 14360 6344 8016
 22420 10988 11432
 9678 4419 5259
 46829 24638 22191
 12598 5654 6944
 14822 6765 8057
 18450 8340 10110
 29898 14173 15725
 20109 8707 11402
 56555 29306 27249
 31592 13842 17750
 24348 11304 13044
 41566 19754 21812
 72249 35761 36488
 9384 5054 4330
 248250 131938 116312
 6384 3368 3016
 8670 4577 4093
 9376 4940 4436
 17248 9103 8145
 4453 2297 2156
 58796 32225 26571
 5080 2691 2389
 7947 4239 3708
 7938 4206 3732
 16218 8633 7585
 1225 634 591
 74616 40803 33813
 9 4 5
 98 53 45
 940 502 438
 7162 3882 3280
 1009 543 466
 810 423 387
 1146 562 584
 3333 1744 1589
 134644 73898 60746
 71 38 33
 1268 726 542
 1008 552 456
 1194 632 562
 4184 2247 1937
 148996 83126 65870
 1846 1008 838
 1593 947 646
 2736 1662 1074
 73352 45167 28185
 25697 14869 10828
 26139899 16713019 9426880
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
17 231 1 4
2 47 0 2
5 67 1 1
6 96 0 2
7 82 1 0
7 102 351 71
74 155 934 187
695 218 1273 460
4458 280 1805 834
16804 366 2722 1486
41368 475 3437 2245
95473 718 4920 3591
186965 1205 6822 5235
317602 2050 9413 7958
424774 3470 12875 11638
495463 5660 17990 16632
476595 8680 23883 23108
389490 13019 31609 31389
280867 19162 41705 41438
177497 26901 52741 52960
113079 36719 64731 64847
94788 50077 77071 77247
101845 67023 90584 90835
114933 83285 105072 105473
130104 100780 118812 117874
142317 116516 130118 129943
150328 127675 140403 139317
154223 134317 145048 144961
152924 138424 144376 145080
148993 137559 142893 143172
143237 135429 138619 138805
138214 131594 135439 134835
133137 128841 131514 130136
129380 125528 127967 128069
126810 124590 125945 125356
124455 122819 124020 123250
124423 122807 123725 122844
125607 124312 125564 124501
124548 124418 125342 123762
124976 124361 124895 124932
125326 125670 126223 123591
124961 122945 124624 123368
120152 120129 120814 119870
114238 112106 114033 112433
105258 104623 105357 103857
91570 90545 90454 91465
69010 68689 68843 68732
64002 63971 64157 63710
59464 59976 60027 59486
55307 55211 55947 55641
48318 48389 48576 48692
39752 39471 39697 39773
30386 30216 30388 30421
21427 21183 21068 21355
13966 13867 13715 13668
7600 7700 7671 7634
2290 2339 2267 2387
74 83 87 89
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
