A = [
601603 609300 3240073 667138 648400 615558 597509 623226 607352 648696 712424 823266 1016296 1199995 1320886 1438098 1608330 1780912 1827705 1828129 1926827 2003935 1999631 1976260 1998864 2130829 2087018 1990909 2031333 1586680 1526358 1418900 935517 935061 924099 913794 904730 879616 878390 882838 870595 874295 871469 868429 882789 860979 848051 879384 850753 846006 838785 799621 811329 812300 788496 759487 776789 786911 752021 731647 737700 724482 710293 691709 679526 677186 656527 644952 635896 621711 614599 613830 606152 600679 602921 594025 586423 584657 570845 556359 552986 546347 533755 525381 525088 508513 491496 473066 461198 455324 447900 438735 434271 426837 423645 417172 411120 405074 400146 392443 388611 380880 374932 368839 362244 358832 354299 348998 345288 339973 335262 333806 329827 324345 323770 319621 396729 398874 397217 471685 476625 472154 465965 461899 454439 447104 440749 435094 426132 417894 410072 402080 395280 388924 382371 376933 369771 365746 356810 350961 345443 339051 332262 328092 321781 315852 310264 305484 300262 293806 289165 283907 280216 274117 267623 263879 258475 253721 248130 242914 241030 235437 231504 228317 222581 217714 215543 211433 208027 205164 201587 198097 194893 190099 187723 185106 181373 177407 174262 171487 169334 166504 163668 160418 158049 156656 152080 150191 148857 146667 144001 141038 139634 137698 134850 132250 130614 128944 126948 124288 122551 120627 118952 117558 115617 114193 111959 110753 108806 106135 103604 102182 100085 97680 97174 95966 94950 94348 92417 90948 89873 89126 87012 85410 83167 80499 79257 77555 75449 73276 70924 70156 69155 67688 66524 65395 63975 62882 61603 60566 59797 58520 57789 56827 55842 54656 53723 52734 52443 51164 50254 48830 48459 47270 46715 45623 45288 44939 43562 43204 42804 41375 40885 40393 39532 38849 38375 37703 37385 36189 36272 35619 34668 34473 33549 33231 32344 32447 31363 31064 30279 30110 29792 28910 28916 28395 27744 27479 27011 26606 26113 26198 25622 24610 24629 24459 23707 23469 23030 22644 22107 22003 21651 20802 21094 20627 20335 19977 19772 19177 19016 18708 18288 18448 18176 17553 17248 17077 16838 16607 16433 16058 15953 15718 15620 15282 15115 14369 14377 14206 14205 13486 13459 13087 13143 12920 12626 12786 12479 12108 12229 11963 11558 11521 11230 10950 10832 10976 10315 10393 9966 10045 9884 9867 9592 9592 9410 9222 9046 8900 8795 8648 8438 8462 8208 8295 8095 7838 7877 7668 7545 7572 7351 7226 7096 7057 6944 6837 6757 6487 6484 6267 6300 6299 6022 5941 6046 5800 5625 5482 5792 5454 5389 5439 5473 4965 5199 5049 4889 4852 4681 4833 4568 4630 4444 4363 4351 4279 4222 4144 4075 4110 3918 4035 3883 3712 3641 3672 3746 3638 3517 3423 3508 3435 3264 3084 3213 3088 3144 3159 3054 2894 3018 2834 2819 2800 2695 2782 2669 2628 2634 2554 2585 2517 2409 2426 2376 2306 2289 2260 2287 2284 2335 2153 2157 2078 1839 1984 2072 1945 1945 1917 1877 1800 1749 1829 1724 1799 1668 1750 1784 1603 1659 1685 1529 1463 1533 1519 1508 1448 1452 1440 1375 1317 1326 1347 1349 1306 1334 1199 1246 1302 1268 1174 1230 1074 1140 1062 1153 1114 1033 1067 1112 1038 1000 1061 981 966 978 943 878 953 868 986 797 938 799 856 817 831 752 761 730 779 747 765 746 775 696 706 642 670 636 698 626 634 630 548 598 647 624 609 579 573 518 565 506 573 562 552 533 547 470 472 497 447 496 454 490 457 412 459 417 445 457 432 436 392 470 400 387 332 358 415 408 378 411 340 328 345 341 341 368 300 332 361 323 327 334 321 290 309 246 284 315 258 282 284 324 289 235 289 273 257 272 291 265 238 267 244 264 239 212 253 207 222 226 222 246 207 225 217 193 204 215 206 202 226 171 182 175 191 195 156 165 179 155 149 146 167 186 166 178 151 157 177 168 118 138 170 163 131 156 175 167 142 158 162 151 129 140 115 130 118 146 127 117 127 143 122 125 119 108 125 106 148 114 118 92 93 95 126 98 83 89 114 96 103 96 101 92 90 97 107 76 92 103 76 89 107 97 97 107 90 83 111 93 89 93 78 78 96 95 89 82 74 63 60 83 63 75 75 69 89 80 98 80 75 71 77 79 73 66 89 91 78 67 76 74 65 113 49 72 88 62 52 71 63 78 73 47 66 75 47 64 65 63 84 62 55 58 49 58 61 61 53 42 57 59 67 43 71 50 47 39 59 35 28 52 40 45 43 52 44 47 46 58 53 29 59 51 41 42 35 49 38 43 38 50 57 52 26 42 43 39 41 41 56 31 56 51 49 57 37 58 48 41 45 32 34 37 38 36 41 44 48 23 47 30 51 37 49 39 35 30 49 35 44 46 24 45 43 44 26 32 37 33 26 34 46 44 32 27 31 31 23 26 28 32 28 31 33 37 48 26 36 29 38 37 18 30 33 25 37 22 40 28 28 23 28 23 25 31 22 25 36 28 19 30 29 28 42 11 12 36 33 24 22 26 15 22 20 30 24 25 25 28 35 22 26 31 15 14 21 17 31 33 24 25 23 20 14 27 23 23 23 21 31 16 22 31 29 33 22 19 20 19 16 23 16 10 23 23 21 15 29 19 11 20 12 18 30 22 13 28 17 13 18 18 19 31 19 16 18 32 23 10 21 20 24 21 13 10 21 22 16 23 21 14 10 17 12 20 18 18 18 13 19 17 26 15 15 13 17 16 22 13 7 9 14 20 15 17 17 13 16 22 13 19 22 23 20 15 30 9 19 12 13 10 6 11 18 21 16 15 19 11 18 14 14 10 12 19 15 12 18 14 16 8 11 9 16 15 14 16 20 15 22 6 3 20 9 12 26 15 11 21 14 15 12 18 19 14 15 27 17 22 15 21 21 24 21 23 24 17 16 23 19 21 20 26 14 16 18 21 17 31 20 16 25 26 25 22 18 17 26 22 35 16 29 25 18 28 33 23 31 34 44 58 43 59 59 61 41 51 3552 90 71 53 47 29 26 31 13 22 13 8 8 13 10 12 13 13 12 15 24 16 9 16 17 12 10 20 8 12 12 16 8 14 10 4 11 9 15 14 8 16 25 15 12 21 36 48 48 47 38 50 21 13 16 6 8 7 18 15 13 12 16 10 12 12 5 10 7 48 10 2 13 10 11 4 5 7 16 9 8 6 7 15 6 5 10 8 6 9 4 5 6 2 12 8 9 6 12 12 10 17 13 5 10 5 9 7 11 6 10 15 12 11 8 11 11 9 23 8 15 7 4 15 12 18 11 11 14 16 14 14 16 11 15 13 11 17 17 18 12 13 12 14 18 12 18 20 12 13 15 22 13 10 12 12 17 16 19 14 11 16 16 7 15 7 10 16 13 12 15 10 16 11 13 10 13 13 15 10 19 8 10 5 16 12 12 17 11 17 18 14 15 10 18 13 16 15 12 9 6 6 12 14 7 10 14 16 18 17 19 11 13 13 5 6 6 6 9 6 9 9 4 10 5 8 6 2 1 13 9 3 12 6 6 11 7 5 7 7 5 5 2 7 7 4 7 4 5 10 4 2 9 11 3 7 6 12 5 3 4 2 5 4 3 4 6 3 2 5 4 3 4 3 4 1 6 6 3 10 4 7 5 7 7 2 4 14 7 6 2 3 6 3 6 4 2 6 11 23 6 3 10 8 15 1 3 9 13 2 7 2 7 7 5 4 6 3 7 7 0 1 6 1 4 5 5 1 5 8 10 3 6 6 14 1 2 1 6 6 5 3 2 2 5 8 11 2 16 2 5 2 2 6 3 5 1 1 3 3 8 5 4 9 5 6 9 10 10 10 4 6 5 6 1 19 7 3 8 5 6 1 3 5 5 14 6 5 7 6 7 6 3 7 10 3 11 11 3 4 3 7 6 8 7 10 3 2 6 7 9 5 12 4 4 9 7 4 8 2 2 2 9 7 6 4 6 12 4 10 13 6 11 12 17 6 11 10 12 6 8 9 8 8 9 6 13 16 8 12 11 9 15 10 8 8 14 5 19 20 11 17 12 17 11 6 14 12 7 11 15 10 6 7 9 10 17 7 8 2 1 4 7 7 5 7 5 4 6 4 1 2 4 2 8 7 5 3 4 4 2 7 8 1 1 3 6 3 0 1 5 3 3 5 2 2 10 2 1 1 3 1 2 1 3 1 4 8 2 3 4 8 1 0 8 3 7 2 1 0 5 3 3 9 1 1 1 1 0 1 4 6 6 4 2 1 5 4 3 3 2 1 4 0 3 5 6 4 2 2 5 4 2 0 0 3 3 2 1 3 2 2 2 0 5 2 5 1 4 1 1 2 0 0 4 3 1 2 3 1 1 1 0 5 0 0 2 2 4 1 1 2 1 1 2 2 1 2 2 1 1 3 3 0 1 1 1 2 2 2 1 0 1 2 4 1 0 2 0 1 2 4 1 2 0 1 0 1 2 2 0 0 2 3 1 1 1 1 0 2 0 2 1 0 3 2 0 1 1 2 0 3 0 3 0 2 0 1 6 1 3 4 0 1 1 0 0 0 2 0 2 2 1 0 0 1 0 0 2 0 0 1 0 2 0 1 1 0 0 0 2 1 0 1 2 1 2 0 2 1 0 2 0 3 2 0 1 1 3 2 0 2 3 0 0 0 2 1 0 0 2 4 1 0 5 0 2 2 4 2 1 4 1 4 4 4 1 0 2 3 3 1 1 1 1 3 3 1 3 2 0 3 4 2 3 2 1 1 1 3 2 1 4 0 1 2 5 2 1 1 3 0 2 2 5 1 1 2 1 3 1 8 3 2 3 0 1 0 0 3 0 3 0 4 1 4 1 1 2 2 2 3 3 1 3 0 0 6 1 2 0 4 0 2 1 0 0 1 1 2 1 1 3 2 1 2 2 2 2 1 0 2 1 2 0 0 2 0 0 1 2 2 1 4 0 1 0 3 0 1 0 1 0 4 1 0 2 0 2 0 4 0 1 1 1 
];
B = [
0 0 0
 348947 244266 104681
 503876 367368 136508
 454606 346830 107776
 378573 285810 92763
 320248 242401 77847
 279725 218976 60749
 224129 178449 45680
 232431 184001 48430
 267297 203414 63883
 325890 247343 78547
 332226 256355 75871
 284708 219996 64712
 255636 195457 60179
 265561 205586 59975
 295095 229950 65145
 266460 208487 57973
 316043 253010 63033
 260628 206652 53976
 272493 216621 55872
 307418 244550 62868
 290979 232222 58757
 297063 238434 58629
 350028 283612 66416
 287506 230366 57140
 325992 262155 63837
 335114 269717 65397
 324394 261625 62769
 289402 233498 55904
 382631 311691 70940
 316954 255708 61246
 320696 259760 60936
 358844 292353 66491
 301779 244817 56962
 419177 343136 76041
 309203 251210 57993
 310621 252535 58086
 805058 664187 140871
 305097 249368 55729
 367095 301891 65204
 694596 574380 120216
 355319 292193 63126
 578256 477875 100381
 367381 303142 64239
 347315 286927 60388
 576738 477055 99683
 430602 357963 72639
 552019 457836 94183
 326267 269080 57187
 704719 591345 113374
 327108 270780 56328
 527829 440052 87777
 638234 542949 95285
 515616 431532 84084
 317935 264419 53516
 1068153 919698 148455
 466240 391761 74479
 297249 248076 49173
 471259 397239 74020
 234005 195234 38771
 41749891 38322700 3427191
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 13 0 0
0 1 0 0
2 3 0 0
2 4 0 0
11 5 0 0
8 5 6 0
52 13 23 3
378 8 39 12
81438 9 56 13
970629 30 84 35
2139742 24 96 58
3751530 37 125 78
5271615 92 307 180
6349270 142 763 427
6092972 229 1106 920
4936018 630 2669 2462
3045172 1387 5607 5411
1672625 2541 9248 9410
944676 4411 14419 14349
471165 6842 19459 19106
191467 10431 24411 24169
68009 15026 29519 29693
41447 21565 35623 35935
45604 30163 42339 42463
53877 39925 50048 49919
61379 50977 59067 58539
70481 61363 67297 67391
79388 72000 75527 76252
87380 81121 84193 84279
93649 88827 91080 91711
99376 94593 96880 97083
102693 99237 100913 101308
104483 101084 102974 103091
105052 102982 103807 104138
110022 104152 104293 103856
106258 104442 104375 105395
104722 104366 104706 105703
105768 105571 105923 105549
106677 106253 106682 107000
108493 108440 108157 108160
109357 108888 109342 109621
112450 111674 111586 112274
115618 115573 115607 116089
120501 119224 118857 119852
124184 124973 125151 125238
129613 129561 128893 130227
136131 135616 135560 134751
139559 139930 140018 139775
143591 144238 144189 144789
147967 148009 147956 147709
150237 150342 149619 150634
149966 149857 148845 150461
148327 148714 147884 148880
144608 144890 145374 144736
138560 139255 139480 140724
132701 133016 132665 133542
124237 124755 124416 125316
115336 114986 115285 116214
104487 105203 104576 104956
96084 95670 95083 95861
86085 86420 85849 86261
78460 79017 77969 79313
70338 70297 70665 70789
65388 64914 65250 65335
61145 61388 61169 61560
59643 59450 59390 59965
58751 59338 58916 59657
61681 62653 59007 58907
56400 55755 56317 56418
56973 56759 57816 57115
55576 55896 54773 55568
52880 53071 53205 52755
50122 49876 50353 50200
43567 43246 43570 43541
36859 36850 36821 36948
30364 30473 30857 30618
23383 23688 23272 23261
15552 15239 15292 15586
11873 11941 12111 12068
8842 8938 8945 9125
5094 5113 5147 4865
3440 2551 2665 2704
135 124 144 116
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
