A = [
1556854 1540856 7475073 1585150 1628069 1541768 1486175 1611347 1560070 1635225 1829117 2154738 2694819 3171042 3579287 3910382 4306049 4681527 4652475 4537144 4726576 4836020 4708725 4589977 4636173 5219527 5251957 5178308 5513542 4153512 4057470 3870586 2537962 2545410 2508523 2496970 2468572 2383226 2377752 2376297 2337873 2340058 2344414 2323748 2348803 2297795 2261982 2329795 2251681 2235716 2233974 2121829 2158045 2146514 2082351 2023322 2049395 2080438 1972083 1916143 1941991 1897980 1862453 1825559 1797864 1792122 1745459 1706186 1691454 1647479 1623398 1619221 1591326 1582364 1586326 1559223 1542123 1532837 1494686 1456100 1438239 1423856 1385628 1363879 1361275 1318277 1277541 1222254 1187157 1173924 1150041 1126926 1116427 1094151 1076588 1064862 1050089 1036303 1019717 1000515 990098 972844 953698 941712 929406 918312 907851 892802 879970 871270 858062 857737 847546 836775 836078 829506 1054591 1066217 1058923 1280422 1296834 1285488 1267180 1252043 1227780 1210972 1190417 1170508 1149184 1131451 1107886 1087031 1065010 1046520 1029937 1009920 990772 978518 958017 940509 925159 909720 891780 877577 860942 844579 829442 814907 799011 785763 771497 758007 743340 728037 712490 700854 686294 674322 659402 650935 638463 626961 612895 602255 589311 579577 570782 559560 550275 540659 530266 521738 512108 504215 495494 486547 477936 470173 460364 452790 443317 436762 430840 422501 416082 409796 401174 395551 389297 383213 378492 370500 365846 358723 353194 346106 341077 335466 329927 324343 320233 316232 311277 304732 301120 295217 291504 285430 280579 276150 270154 265891 260585 256006 252864 250217 244566 242893 238253 234307 231873 226826 223971 220189 215009 209676 204929 199794 194774 190913 186226 182344 179331 175301 172248 168933 166799 162857 159735 157419 155264 152022 149021 146864 143777 141618 138548 136179 134168 132020 128927 126938 124834 122511 119596 118247 115862 114026 111854 109814 108549 106124 104631 102478 101352 99392 97820 96108 94279 92410 90931 89661 88168 86682 85263 83998 81879 80225 79468 77784 76706 75405 74007 72788 71740 71156 69291 68559 67036 66496 64685 63856 62494 61745 60536 59860 58720 57785 56899 55925 54970 53734 52890 52148 51195 50416 49802 49009 48211 46961 46356 45463 45169 44101 43506 43098 41974 41245 40593 40029 39516 38958 37806 37284 36716 36299 35891 34726 34509 33637 33662 32809 32378 31903 31019 30779 30103 29786 29335 28741 28153 27812 27480 27014 26746 25794 25547 25078 24777 24515 24119 23854 23587 22850 22358 22090 21629 21537 21177 20903 20716 20022 19513 19447 19025 18872 18390 18208 17990 17497 17563 17253 16805 16483 16248 15791 15887 15315 15158 15035 14805 14434 14332 14095 13891 13481 13304 13308 13081 12913 12390 12257 12090 11798 11677 11500 11326 11145 11002 10751 10806 10476 10274 10039 9915 9796 9729 9478 9463 9169 9108 8975 8829 8844 8496 8164 8084 8096 7817 7852 7818 7636 7703 7449 7089 7149 7153 7115 6867 6778 6568 6615 6393 6319 6267 6086 6088 5971 5854 5749 5685 5531 5440 5429 5351 5256 5156 5095 4931 4853 4831 4764 4560 4709 4500 4469 4595 4313 4260 4135 4148 4041 3977 4057 3918 3829 3877 3606 3721 3645 3669 3502 3439 3411 3390 3406 3181 3294 3087 3182 3133 3014 2885 3026 2917 2895 2763 2761 2678 2662 2614 2598 2568 2549 2547 2483 2386 2440 2290 2393 2352 2317 2248 2120 2222 2090 2092 2029 2053 2015 1977 1978 2006 1905 1889 1886 1805 1868 1706 1833 1722 1629 1653 1591 1671 1599 1448 1599 1585 1492 1484 1512 1481 1390 1404 1421 1387 1345 1304 1251 1275 1250 1228 1331 1239 1238 1209 1247 1139 1119 1104 1203 1082 1102 1073 1036 1056 1072 1083 1083 974 955 948 968 953 945 879 908 897 868 881 897 855 817 779 818 810 756 791 779 745 766 740 750 776 686 715 689 691 700 668 677 745 787 721 708 687 688 647 611 657 596 578 584 570 533 555 560 578 582 543 598 527 535 511 526 508 536 505 527 490 512 541 490 456 486 475 471 467 443 471 430 437 435 414 397 419 424 403 423 395 419 418 358 421 372 353 391 360 357 393 369 369 338 364 385 358 372 335 355 355 319 334 324 359 332 305 339 286 316 303 313 313 300 294 289 297 280 297 309 284 299 274 289 252 278 271 269 263 295 269 223 265 237 283 247 229 253 266 221 239 251 215 250 222 279 236 265 234 234 226 224 199 222 230 198 224 208 211 228 204 172 186 183 193 193 184 198 199 178 205 202 195 197 192 176 173 213 197 174 202 183 176 176 175 181 168 169 165 156 161 160 166 157 152 157 167 151 172 148 130 159 157 161 161 158 134 163 152 150 130 146 130 157 150 143 144 149 146 140 122 159 130 159 126 118 140 123 138 122 127 132 117 130 131 97 119 118 123 130 116 105 129 141 141 138 113 117 138 129 132 107 113 108 132 142 117 115 107 133 127 115 115 121 112 102 102 112 117 119 106 85 98 119 97 95 84 84 89 80 103 105 105 108 102 87 102 101 82 118 75 97 99 105 103 89 79 84 85 82 73 100 90 82 84 88 86 92 79 97 88 81 63 87 80 80 75 75 73 71 74 95 84 90 79 76 90 73 75 75 81 72 70 64 68 65 59 81 69 52 55 63 70 84 70 82 66 68 83 86 58 81 66 78 76 81 53 83 67 82 78 59 58 81 66 75 62 67 63 68 68 56 73 58 81 75 54 52 62 72 61 61 57 54 68 64 70 54 52 47 66 50 44 52 64 51 65 58 56 46 57 48 51 49 50 41 39 59 52 56 60 66 36 59 50 53 48 51 50 50 58 44 39 55 55 45 30 34 51 38 52 42 45 42 45 50 33 57 35 49 49 42 40 49 49 49 48 42 37 45 47 57 50 46 50 54 48 45 55 51 50 36 52 43 46 50 43 59 49 44 42 45 31 33 27 38 41 49 48 36 48 37 56 31 42 30 30 51 40 39 53 59 68 93 162 190 200 252 219 211 223 206 213 238 322 180 137 147 160 173 128 146 155 163 136 139 153 121 144 135 138 123 119 157 148 162 142 140 152 161 130 145 156 145 163 144 165 156 160 163 195 170 161 189 177 273 222 231 214 231 215 231 219 240 270 697 296 243 196 213 144 189 154 96 96 96 91 103 123 103 110 102 105 100 83 79 85 95 65 70 48 77 75 67 66 90 67 69 67 75 83 70 94 95 103 105 114 208 268 1190 943 810 462 429 335 369 323 209 140 115 67 67 73 89 76 66 82 66 96 66 68 71 142 103 492 36 37 32 34 27 25 25 26 26 30 25 16 21 23 22 21 19 30 15 25 33 23 26 34 29 31 39 31 31 24 31 30 47 47 44 34 59 53 43 35 42 40 36 28 55 51 47 58 50 63 63 56 62 63 65 58 47 54 58 57 67 71 77 64 59 56 70 84 83 88 78 83 68 87 84 68 77 76 80 79 97 74 94 75 78 92 91 86 100 94 102 80 89 89 77 88 90 102 125 109 93 108 94 94 94 99 110 101 88 91 95 92 109 93 99 96 92 105 79 113 99 89 113 96 71 100 124 92 99 71 80 75 100 88 67 72 102 90 94 61 73 48 44 51 44 50 44 50 54 44 108 75 103 158 61 47 45 40 29 32 32 39 29 35 57 33 43 28 40 34 36 34 39 40 40 55 37 45 40 38 41 39 48 68 51 57 38 51 59 38 44 52 56 58 61 53 50 38 33 39 54 43 44 30 40 45 53 48 43 54 43 53 51 42 43 47 54 57 36 52 50 54 52 47 34 43 32 43 37 46 28 29 36 167 43 39 35 38 30 33 26 32 21 33 36 24 19 20 25 25 22 18 21 15 16 18 29 30 17 24 28 26 15 19 23 19 23 16 19 15 23 15 18 16 11 19 17 19 17 14 18 20 19 26 26 18 16 26 19 16 17 24 22 20 26 26 26 20 22 23 21 19 20 14 14 21 18 14 14 18 12 13 16 9 9 11 15 7 16 13 13 9 17 15 14 12 9 12 17 15 13 10 15 12 10 6 12 18 15 14 14 13 10 19 23 15 23 15 21 20 15 9 21 19 23 15 22 21 22 20 18 26 29 22 28 16 18 22 29 16 19 17 21 33 20 28 31 33 32 31 25 24 19 30 30 21 27 17 26 16 30 28 27 27 25 24 22 24 30 25 31 27 35 28 25 36 34 25 22 23 21 18 22 20 30 31 20 20 15 23 23 20 20 20 18 22 14 23 22 11 14 19 21 28 19 19 18 19 17 19 21 25 18 21 20 13 21 21 18 17 18 26 25 19 29 19 22 19 16 18 18 11 9 12 11 17 12 13 6 12 7 11 15 7 7 12 6 11 10 8 11 9 8 8 8 10 5 10 8 4 8 6 12 8 7 3 4 12 3 4 9 8 4 6 2 7 10 3 10 8 10 9 9 7 3 10 5 6 7 15 9 7 7 9 5 10 7 11 8 3 4 7 2 6 8 5 7 5 8 3 8 8 6 8 6 6 6 11 8 10 5 7 7 6 5 8 7 6 5 7 3 4 8 6 5 9 5 4 5 6 4 5 3 3 8 7 4 1 6 4 6 5 9 4 4 8 4 12 7 3 5 7 4 8 4 6 4 2 8 4 4 4 5 7 5 4 6 7 10 9 7 5 7 8 7 6 5 1 6 7 5 3 5 5 6 2 3 2 4 1 1 2 4 4 6 3 2 5 7 3 4 7 7 4 7 5 4 3 4 7 3 3 3 2 3 5 6 4 8 5 1 4 5 6 3 5 5 3 3 2 3 3 3 5 4 5 6 2 4 2 1 6 1 3 9 8 10 4 12 4 7 3 4 5 6 13 8 6 13 5 7 11 8 3 11 4 2 11 9 14 6 7 5 5 7 8 3 7 8 8 5 8 6 4 6 2 9 2 2 4 4 7 5 4 6 3 8 6 3 3 6 2 4 6 6 3 4 6 3 4 6 6 7 3 3 4 3 8 8 4 5 6 6 9 7 4 4 5 7 4 3 5 1 10 3 3 9 6 5 2 5 3 2 4 2 7 2 4 4 7 2 3 5 1 2 4 4 5 3 6 6 2 4 10 3 3 4 4 4 4 5 3 5 5 6 
];
B = [
0 0 0
 882997 572492 310505
 1266976 889135 377841
 1069735 772811 296924
 919002 663536 255466
 813421 597311 216110
 645615 489977 155638
 566871 438944 127927
 521191 403116 118075
 579175 431165 148010
 901577 674387 227190
 767622 574734 192888
 754091 571077 183014
 714211 539161 175050
 685423 521690 163733
 806359 624918 181441
 748624 582652 165972
 804801 637872 166929
 732509 578281 154228
 769052 609526 159526
 859972 684531 175441
 827049 659281 167768
 836079 672662 163417
 837468 675420 162048
 809570 650553 159017
 909134 733395 175739
 800997 644435 156562
 919579 744323 175256
 805997 653873 152124
 870609 708255 162354
 878365 711307 167058
 909678 740598 169080
 871161 709927 161234
 842222 686621 155601
 1065733 874157 191576
 847850 693958 153892
 864800 708035 156765
 2223562 1831489 392073
 822814 675347 147467
 993692 820504 173188
 1784540 1474850 309690
 943768 780087 163681
 1588615 1317314 271301
 803111 662965 140146
 940808 781142 159666
 1597346 1329528 267818
 938695 781585 157110
 1527659 1275249 252410
 914498 762222 152276
 1470017 1230575 239442
 908827 760041 148786
 1445255 1213038 232217
 954261 802114 152147
 1428676 1203259 225417
 902635 759005 143630
 1515788 1283235 232553
 1334594 1129813 204781
 835730 706887 128843
 1339267 1138230 201037
 649670 550623 99047
 109514052 100737354 8776698
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
13 33 0 0
2 9 0 0
6 13 1 0
14 21 0 1
14 13 1 0
24 14 2 1
28 29 1 1
141 20 6 3
330885 37 5 6
3125685 60 12 13
6018744 80 31 15
9818975 107 83 51
13212026 144 485 189
15553968 262 1680 746
14607836 529 2423 1868
11771601 1665 6721 6247
7613712 3883 14766 14719
4222991 7021 25729 25094
2164524 11934 39010 38596
915409 18898 52018 52424
328649 28137 65919 66041
137557 41409 80487 81082
109675 60101 96696 97220
124860 82823 115899 115546
145076 109517 136656 138163
167923 138975 159890 161105
193896 168818 184599 184347
218380 197317 209433 209505
240923 222732 231751 232854
259412 244013 252911 253235
274103 260858 267990 268200
281995 272834 276099 277785
286785 278787 282569 284863
289306 284496 284971 287023
289522 286049 287619 288270
290577 288088 289596 288920
290482 289586 288437 290971
292582 290918 290775 291528
294279 292775 293434 295051
297343 296922 296724 298892
302981 301899 301837 303121
309257 307558 307830 310444
318607 317408 317305 319159
330247 329608 328450 330727
343844 342997 342598 344362
358657 357916 356946 359541
372689 372588 370997 372950
385806 385564 385690 388672
399577 399309 398718 399702
408218 408179 407435 409862
415271 414893 414426 414432
416307 415659 415174 417563
410916 410453 409351 413278
403286 404227 402646 404925
386906 388865 387184 389946
370004 370513 368644 370278
347280 349208 348189 349022
322636 322615 320984 323476
293639 294427 292536 295802
267323 266342 266926 267622
241473 241780 240914 242342
219385 220324 219619 220757
198472 197235 197293 198729
182149 182627 181878 183003
172738 172584 172918 173239
166194 166167 165576 166293
165933 165305 164359 166449
165010 167066 164505 166261
157348 157609 156594 158118
159412 159296 158976 159618
155552 155278 155155 155716
147939 147112 147449 148354
139250 139077 139561 139928
119862 121056 120184 120163
102160 101791 101784 103100
84579 84592 84260 84645
63802 64067 63792 63882
41778 41728 41921 42038
32021 31876 31647 32425
23586 23764 24033 23712
13526 13608 13473 13593
6589 6687 6780 6532
313 349 337 335
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
