A = [
1048023 1023846 5011940 941297 930569 897689 892127 902969 887403 868238 866879 858539 850625 840870 845205 837622 836279 832417 830610 828030 826489 820665 820703 852816 939247 1272903 1296607 1371853 1703831 1716565 1757417 1777335 1787261 1836742 1839034 1830622 1802762 1784149 1768973 1745250 1740343 1729289 1712995 1713365 1700950 1682800 1674124 1654483 1627873 1620569 1606452 1588770 1583691 1567211 1557370 1549192 1531084 1510576 1501138 1484114 1464165 1456114 1442328 1425226 1420992 1405913 1386342 1380725 1365307 1347461 1335448 1323139 1304422 1294846 1284043 1270766 1262445 1243757 1227341 1216442 1201944 1185438 1177315 1163633 1150402 1144501 1131067 1118049 1110194 1092362 1073824 1067895 1055342 1039920 1038475 1025084 1008893 1002404 993496 975859 968983 957587 942419 934608 923780 911359 904892 893005 880701 871250 862349 848773 840227 830273 817432 810660 799300 788803 779342 770960 759827 748586 738366 726875 722607 711402 704184 698088 687493 676353 668934 658291 647706 642466 633620 621738 617944 608154 597363 593513 586176 573686 570391 561621 552046 549410 539384 530669 524444 517508 513342 504979 498838 490395 486419 479672 472977 465931 461372 455591 449966 441743 434168 430878 424479 417785 411393 406515 401900 397035 392853 385653 380560 374524 369800 364134 358833 354114 350417 346289 337997 336522 334648 325869 321676 317573 313690 309948 305950 300118 297476 292475 286773 284661 282272 275742 270716 268440 265727 261790 256982 254306 252027 247542 243051 239311 236451 233199 229764 226336 221758 218965 217768 214007 210112 206078 201923 200723 197627 194230 190133 186209 184115 183236 180054 177421 173084 171095 169195 166651 163884 159954 158553 156828 152746 150666 149477 146890 145257 142718 140567 137813 134917 133659 131724 130385 127535 124954 123625 121998 120222 117036 115881 114139 112884 110705 109064 106696 104421 103958 101646 100045 97876 97344 96268 94195 92140 90329 89574 88107 86719 85793 84246 82735 81849 80010 78858 77303 76515 74551 73758 72505 72086 70780 69834 68326 67533 66436 64627 64462 63113 61849 60465 60250 59191 58333 57779 57067 56012 55172 53815 53395 51968 51398 50406 49853 49126 48334 47335 46217 45278 44657 44091 43423 42409 41620 40892 40369 39282 39007 38402 37992 37605 36539 36628 36359 35372 34961 33955 33684 33069 33042 32093 31604 31354 31238 30593 29937 29472 28785 28646 28204 26850 27048 26314 25629 25358 24362 24276 24199 23642 23324 23024 22561 22376 22008 22446 20926 20938 20233 20121 19441 19223 18768 18820 18569 17936 18179 17631 17171 17392 17196 17144 17090 16603 16470 16174 15718 15461 15476 15670 15215 14484 14563 14474 13962 14110 13884 13566 13383 13082 13155 12965 12488 12457 12152 12025 12115 11762 11491 11606 11097 10599 10796 10423 10098 10033 9831 9798 9636 9519 9239 9242 9152 8875 8700 8828 8569 8440 8529 8453 8337 8331 7999 7840 7787 7839 7505 7256 7307 7457 7184 7140 7043 6957 6771 6622 6696 6481 6513 6373 6136 6096 6132 5899 5918 5936 5956 5781 5746 5680 5355 5571 5319 5442 5366 5399 5114 5067 5026 4973 4816 4854 4646 4766 4579 4511 4434 4424 4553 4550 4361 4413 4353 4145 4030 4173 4200 4024 3838 3921 3929 3705 3684 3658 3614 3522 3526 3421 3370 3589 3506 3402 3263 3267 3335 3355 3276 3269 3229 3097 3061 3047 3025 2904 2960 2857 2873 3089 2787 2786 2953 2910 2838 2856 2665 2856 2719 2617 2617 2754 2681 2544 2614 2518 2352 2334 2490 2369 2367 2367 2238 2246 2174 2159 2168 2110 2050 2166 2231 2251 2027 2156 2035 2031 2005 2082 2109 2008 2059 2031 2007 1972 1911 1826 1980 2020 2040 1901 1975 1914 1839 2107 1924 1890 1888 1761 1808 1920 1891 1818 1791 1812 1796 1805 1612 1689 1763 1678 1601 1732 1648 1616 1529 1519 1495 1523 1651 1501 1486 1463 1460 1469 1386 1430 1405 1368 1467 1425 1442 1329 1238 1165 1255 1345 1371 1272 1262 1244 1172 1040 1071 1083 1140 1094 1105 1140 1048 1134 1059 1034 1072 970 922 960 938 981 982 982 992 991 955 946 863 860 757 774 847 743 802 828 933 980 904 692 716 722 767 659 659 698 621 651 661 721 658 724 644 640 574 620 590 594 714 720 646 597 539 571 631 560 596 549 453 481 454 477 396 377 376 439 476 455 442 430 488 404 436 390 395 438 412 397 343 402 404 429 400 438 377 371 356 370 400 411 368 378 386 405 362 379 443 366 375 381 394 360 364 356 321 287 315 334 274 224 282 290 249 256 256 230 275 239 314 358 345 314 347 347 465 372 296 345 326 317 528 358 311 328 288 323 252 258 281 297 282 293 298 314 372 251 244 217 201 172 183 187 167 186 168 172 167 200 163 190 192 201 185 286 254 229 212 178 204 414 308 287 285 243 324 414 129 129 109 131 127 110 136 121 130 122 116 122 96 94 117 100 135 114 87 88 112 88 104 99 109 112 116 103 94 110 120 114 107 104 126 105 147 201 141 175 163 171 173 192 171 273 200 157 160 177 177 102 120 92 72 73 80 88 97 78 95 125 113 144 151 112 124 117 98 94 156 122 116 103 130 96 123 98 85 72 120 109 129 101 103 109 93 123 61 81 73 69 71 57 47 55 49 56 52 42 33 36 77 87 72 68 124 69 86 94 75 80 115 90 78 44 38 39 46 31 94 52 87 93 67 75 67 33 46 72 81 67 51 65 45 46 67 52 53 37 39 52 38 28 29 47 37 42 44 46 40 41 31 42 55 77 58 56 79 59 57 71 48 48 37 69 87 85 65 51 81 46 64 52 50 65 62 57 40 46 47 45 52 53 54 53 57 63 82 60 47 57 58 35 49 47 58 63 63 36 60 37 44 34 36 28 45 57 35 56 48 35 51 44 37 42 50 34 39 34 44 47 50 38 45 46 40 43 43 54 53 36 33 31 39 31 32 26 13 26 40 31 20 42 31 38 33 23 35 25 33 30 30 32 29 33 25 28 27 29 24 30 22 18 21 25 22 21 34 16 21 19 30 30 25 20 25 25 27 19 17 24 14 26 26 32 19 29 26 29 17 28 30 25 30 32 41 47 24 26 31 29 41 39 41 31 23 25 28 24 30 31 32 52 66 42 40 51 41 52 76 57 40 51 28 47 23 37 41 26 47 62 30 41 42 36 40 30 33 38 21 23 28 18 34 28 32 19 31 38 15 23 12 27 17 18 16 31 21 17 29 16 8 19 12 16 22 17 10 14 19 15 23 9 18 9 11 6 11 17 30 17 21 10 28 24 10 6 12 15 10 12 15 12 16 11 15 13 11 11 15 26 13 21 15 13 22 12 11 19 27 39 34 12 4 10 21 14 16 31 22 16 19 20 21 10 13 12 19 28 9 6 2 0 3 3 4 6 8 7 25 21 4 2 3 5 3 5 7 8 7 1 1 1 3 2 3 8 5 8 5 20 10 16 20 22 6 5 18 16 21 14 5 16 3 19 14 8 21 21 19 18 24 25 23 12 16 22 17 17 21 4 3 3 3 7 4 4 9 8 10 8 13 13 8 10 3 6 13 12 15 12 4 2 5 5 3 5 2 2 3 4 5 4 1 0 2 3 3 0 4 2 2 1 3 0 5 1 3 6 2 3 0 2 4 4 2 1 4 4 1 5 0 4 1 1 3 2 2 0 0 1 2 2 0 1 0 1 1 2 1 1 1 3 3 0 1 0 0 4 0 0 2 1 2 4 2 0 1 0 0 0 0 0 0 3 3 2 2 0 2 0 1 0 0 0 2 2 4 2 2 2 3 0 1 1 1 1 1 1 1 1 3 0 2 1 1 0 1 0 0 0 0 0 2 1 0 1 2 1 0 0 1 0 3 3 0 3 2 0 0 0 0 3 1 3 0 0 0 0 3 2 1 3 2 7 1 4 0 1 4 3 1 0 6 2 10 9 5 5 5 14 13 9 11 8 9 2 6 1 4 7 3 1 3 6 3 4 5 3 3 1 2 4 3 2 0 1 0 1 1 0 0 1 0 0 0 0 0 2 0 0 0 1 0 0 6 5 5 5 1 8 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 2 0 0 3 0 1 2 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 2 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
];
B = [
0 0 0
 101613 12365 89248
 65601 10620 54981
 199461 39568 159893
 47088 4964 42124
 46007 5287 40720
 75736 8942 66794
 72756 9918 62838
 91003 16164 74839
 166175 35464 130711
 50618 5424 45194
 60161 6994 53167
 53470 6840 46630
 116634 19438 97196
 59676 9704 49972
 168034 38115 129919
 65556 8803 56753
 73454 11435 62019
 92922 13224 79698
 191127 30292 160835
 125592 18480 107112
 245947 48986 196961
 202017 23176 178841
 126688 16484 110204
 332820 53915 278905
 362015 57427 304588
 61359 11885 49474
 1152626 259897 892729
 7833 2019 5814
 38702 10218 28484
 18348 4300 14048
 28544 7585 20959
 17386 3576 13810
 127762 36996 90766
 11015 2777 8238
 36468 10251 26217
 17798 4325 13473
 25512 6806 18706
 5062 1258 3804
 138541 41027 97514
 55 20 35
 311 111 200
 4253 1254 2999
 38808 11018 27790
 4600 1283 3317
 3927 1182 2745
 8772 2090 6682
 12014 3197 8817
 211157 64592 146565
 281 106 175
 5427 1821 3606
 4556 1353 3203
 4489 1267 3222
 16834 5023 11811
 222524 71832 150692
 10657 4170 6487
 12023 4858 7165
 36089 18145 17944
 1749572 826749 922823
 77549 31195 46354
 97059461 49718328 47341133
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
27 187 1 0
8 27 0 0
16 37 0 1
17 58 0 1
13 66 3 2
38 61 376 34
1042 111 982 130
6596 121 1259 291
33251 177 1723 487
108185 283 2464 935
221742 344 3198 1441
425339 557 4409 2605
712988 947 6018 4016
1160683 1721 8977 6885
1689325 3240 13399 11632
2323481 5978 20546 18750
2740304 10069 29271 28275
2764348 15624 40802 40222
2241492 25060 55761 55279
1301206 38146 71710 71273
540505 55526 88404 87837
195388 76004 102884 102564
140828 101012 119407 118751
150894 125946 137725 137068
163756 149551 158490 158990
185767 174677 179169 181210
203747 197357 200300 198706
220743 220063 218701 218122
235161 235491 234688 235887
247073 247881 247353 245441
254522 258624 257540 254472
269106 268130 267567 263618
275586 273441 273940 271078
277087 280102 279503 276079
285299 289636 286633 284223
289656 292717 293117 291843
298287 298272 300346 297120
298953 300384 302339 298098
304869 307165 306397 300317
305996 311052 310036 306760
312214 315062 316822 310518
338984 335650 340029 334658
341488 337586 340878 338138
333314 336016 336021 331357
302150 297180 299499 302385
256039 251257 253173 253315
248386 248845 249791 248863
254539 254545 255095 254521
259484 259979 260471 261079
258521 257969 257937 259096
251883 252846 253404 251424
241043 241249 241062 239945
220570 220694 219805 219853
183784 183161 183764 183222
135146 135067 134062 134757
88914 88862 89287 88955
58521 58050 58632 57764
39964 39817 39816 39400
26167 26300 26231 26058
14864 15184 14949 14704
1780 1888 1879 1912
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
