A = [
4790278 5479359 82129009 2521561 2637470 2522745 2256830 2476491 2228878 2016249 2010053 1918842 1915719 1875980 1829193 1822361 1799466 1800594 1801582 1747174 1741840 1755481 1714882 1700021 1694014 1879677 1884509 1896058 2056268 1923166 1957891 1950750 1809707 1819514 1831311 1834825 1821214 1807860 1813892 1814643 1797596 1814299 1812080 1801491 1818188 1794802 1776326 1819492 1791240 1780322 1799899 1749183 1772180 1762364 1727292 1719055 1713223 1728385 1688322 1671029 1695329 1677624 1666256 1661917 1650579 1656773 1634380 1618700 1613842 1599783 1591602 1587985 1570715 1564083 1561302 1542515 1533125 1527695 1505516 1487315 1478025 1472265 1450678 1438071 1439628 1412389 1387430 1354400 1332471 1326596 1310698 1295136 1291112 1274853 1263374 1256773 1247378 1235106 1223216 1212513 1205956 1193531 1185381 1176991 1168908 1158557 1149629 1138920 1131327 1120219 1110266 1107004 1097727 1090923 1084060 1074500 1087141 1082836 1076698 1090619 1090548 1086275 1080727 1076010 1067817 1061639 1050130 1045079 1035841 1027874 1017865 1010244 1004246 996444 990307 981938 972390 965570 957149 947504 941675 931607 925768 917348 909620 902059 894911 887672 879013 871612 862361 855536 849504 840444 831969 826191 816746 809738 801993 794791 787499 782896 773981 766661 761107 752666 748741 739289 732406 725555 718091 715114 705801 702758 694598 690504 681892 676452 670930 664593 658483 652267 648257 641241 637721 631282 624465 619129 613004 612289 604297 598422 592072 587865 583012 575811 571000 566750 561149 555628 551243 547143 541360 536598 530489 526020 522379 516191 512531 507175 501830 496591 492609 485599 482795 477850 474174 469753 465287 461351 456238 452952 446985 443851 438358 432935 428589 426212 419331 414182 410101 406303 401717 395532 390950 386846 382976 378602 375819 371631 368152 362570 359571 357197 352586 349364 346233 341812 338971 334255 330696 327170 323969 321545 317571 312917 310869 307053 302782 300653 297536 294259 291382 287673 284962 281811 278610 274641 273591 269798 266830 263798 261065 258229 255537 252229 250129 247072 244180 241840 239489 236458 233751 232052 228988 225888 223778 222252 219282 216098 213987 212267 208607 207341 205257 202650 199764 198133 195918 193660 192129 189266 187529 185201 183277 180616 178543 177157 175607 172252 171091 168987 167309 165254 163071 161980 159810 157561 156108 154333 153056 150451 148451 147410 145538 143931 142137 140551 138718 136875 135428 134576 132987 130989 129056 128206 126028 125083 124436 122382 120839 118904 118282 116926 115566 114035 112100 111540 110627 108242 107277 106174 105301 103597 102969 101441 100734 98706 97546 96736 95637 94488 93725 92237 91293 90276 89362 87348 86674 85609 85103 83781 82759 82381 80780 80068 78652 78025 76977 75899 75033 73816 73242 72443 71527 70728 69487 68984 68214 66962 66403 65604 65119 64234 63421 62561 61887 60976 60000 59532 58973 57959 57338 56698 55797 55256 54497 53838 53439 52880 51878 51424 51366 50188 49397 48978 48535 47344 47515 46209 46352 45583 45082 44682 44156 43386 42869 42127 41778 41054 40974 40392 39835 39337 39170 37679 38187 37196 37068 36700 35746 35613 35202 34711 34346 34228 33251 33045 32376 32115 31728 31491 31089 30950 30491 30030 29652 29323 28849 28393 28189 27631 27530 27069 26463 26045 25997 25664 25531 25150 24680 24433 24038 23941 23310 23336 22944 22759 22347 22609 21684 21504 21093 20951 20916 20390 20379 20196 19809 19327 19198 19334 18936 18653 18496 18099 17824 17815 17581 17515 16966 16826 16647 16589 16000 15935 15758 15598 14975 15199 15074 14812 14509 14488 14084 14077 14212 13643 13448 13180 13216 13105 12925 12820 12567 12416 12299 12121 11852 11466 11632 11388 11068 11056 11073 10973 10661 10518 10389 10283 10284 10138 9926 9746 9689 9697 9350 9480 9221 9003 9048 8846 8797 8836 8697 8466 8523 8185 8332 8105 7876 7858 7802 7713 7439 7543 7335 7430 7155 7192 6910 6738 6723 6840 6530 6586 6603 6480 6338 6366 6162 6178 6065 6112 5953 5801 5754 5855 5781 5408 5494 5397 5525 5520 5353 5301 5280 5055 5042 4835 4896 4952 4890 4779 4717 4697 4684 4580 4521 4517 4479 4314 4387 4295 4160 4210 4151 3959 4060 3992 4103 3907 3775 3848 3775 3815 3689 3824 3650 3586 3588 3597 3398 3433 3405 3285 3300 3262 3270 3146 3145 3162 3139 3131 2995 2965 3085 3023 2987 2944 2823 2831 2862 2797 2777 2811 2770 2635 2702 2739 2618 2702 2569 2577 2548 2503 2489 2425 2411 2308 2433 2403 2298 2317 2304 2304 2193 2272 2261 2079 2228 2193 2124 2113 2137 2008 2129 2042 2054 1965 2012 1896 1935 1902 1947 1915 1842 1827 1841 1906 1777 1731 1815 1799 1882 1729 1703 1723 1719 1765 1656 1694 1695 1605 1575 1587 1554 1558 1575 1544 1535 1517 1538 1517 1480 1431 1549 1444 1459 1429 1486 1405 1330 1405 1497 1399 1388 1429 1396 1432 1315 1372 1383 1381 1264 1318 1279 1215 1236 1297 1257 1259 1191 1255 1197 1179 1213 1126 1160 1160 1197 1180 1084 1154 1126 1069 1091 1066 1109 1050 1115 1074 1026 1123 1050 1103 1036 1057 1044 1071 1043 1030 1003 1007 1006 964 966 978 900 961 982 950 914 994 985 971 914 887 914 919 950 892 837 877 911 914 971 878 868 831 886 869 872 871 821 901 833 816 775 786 813 833 833 790 791 823 779 794 784 763 728 750 764 774 736 744 704 735 720 737 726 713 703 663 668 736 654 681 644 722 665 654 675 649 650 671 651 606 666 645 644 676 632 632 685 647 616 664 646 653 614 620 614 607 656 621 595 640 588 583 599 594 577 579 571 563 587 546 570 557 540 583 594 527 560 526 558 541 518 511 558 540 535 493 533 549 550 520 540 494 455 559 527 503 507 504 494 474 493 530 447 490 452 502 496 457 496 448 488 480 465 450 484 447 514 447 485 438 430 440 453 489 421 422 463 450 430 435 436 446 445 444 468 436 429 414 445 422 391 399 397 410 426 386 422 405 395 413 417 391 398 413 371 398 423 392 400 398 380 357 376 377 365 370 411 358 368 352 388 403 388 363 357 415 378 373 403 366 365 412 355 368 362 377 334 349 372 337 349 360 316 351 315 350 337 331 300 309 339 347 346 331 339 345 328 316 304 355 332 373 299 338 350 305 328 319 340 331 310 318 302 314 314 326 314 317 324 331 324 306 365 373 440 414 585 634 624 715 678 689 685 703 751 745 819 652 515 556 543 550 562 548 548 507 485 494 507 498 499 487 512 487 478 485 519 487 503 520 498 467 476 484 447 469 453 472 422 458 488 440 483 510 483 507 466 555 585 588 540 588 488 537 564 529 557 1150 609 583 512 466 449 441 433 413 374 376 372 348 387 347 321 343 352 309 292 283 302 307 282 249 315 249 294 281 249 265 298 291 284 269 263 290 282 263 323 322 335 1075 426 1267 1096 1082 761 599 649 605 640 494 432 397 344 314 365 410 287 311 325 310 301 258 216 231 231 277 1150 194 213 202 215 196 220 198 196 206 203 201 177 197 196 194 204 228 191 180 182 199 263 202 190 175 192 265 164 208 191 200 332 186 199 187 189 191 172 171 176 154 183 177 166 176 156 333 184 172 184 187 230 238 176 200 207 214 189 200 220 212 211 178 207 199 192 185 209 210 228 203 178 200 218 197 188 209 202 182 197 208 198 227 196 220 227 217 203 218 213 178 212 217 291 228 205 245 249 245 234 230 208 240 205 213 199 210 221 229 195 196 217 225 230 213 237 215 205 205 239 224 230 227 201 225 230 230 228 223 233 257 222 232 179 208 483 232 221 224 212 511 182 151 170 132 568 145 183 221 197 403 217 250 437 213 253 189 148 124 144 162 150 142 144 135 168 135 118 127 122 143 123 129 138 167 146 142 182 124 123 134 151 172 161 158 164 159 187 170 162 164 150 152 173 162 152 150 138 151 146 137 139 156 138 141 166 129 115 165 144 150 157 158 145 152 154 130 163 175 168 163 173 162 157 132 110 140 139 124 128 128 119 103 233 105 123 112 107 96 84 98 78 87 110 83 78 100 92 101 86 86 78 75 76 88 71 86 78 68 70 70 70 63 59 70 67 59 56 67 65 64 74 62 70 81 69 63 66 58 63 63 75 68 65 64 60 58 57 66 85 61 59 59 55 64 59 72 69 57 58 75 66 73 70 70 74 82 86 67 73 56 66 52 56 54 53 47 53 45 57 58 59 63 55 59 49 53 50 50 49 54 69 67 63 64 66 59 55 65 76 55 70 65 63 57 54 68 62 87 65 55 55 70 51 73 60 62 71 80 71 59 65 65 72 75 66 55 56 47 60 63 84 76 54 70 75 88 86 69 76 61 55 59 56 71 59 62 64 62 84 54 66 65 82 65 79 66 77 72 80 56 68 83 56 69 64 68 60 70 57 73 62 57 66 66 61 73 52 58 79 72 57 56 68 63 49 67 61 60 58 71 56 57 61 54 70 61 42 48 56 72 58 69 41 46 64 58 55 61 57 76 61 54 68 55 59 41 49 52 53 53 48 46 40 52 48 37 53 39 36 43 40 47 40 37 39 31 35 35 41 34 38 35 43 31 35 39 38 27 43 31 47 37 36 31 39 25 36 24 40 33 31 22 21 24 27 34 37 32 19 44 27 27 35 35 43 34 39 34 32 44 34 49 21 34 33 63 25 35 38 36 26 32 35 34 29 34 28 37 35 24 31 31 35 25 42 21 27 30 29 45 20 28 25 24 53 20 26 18 26 32 20 28 28 26 35 37 20 37 27 33 30 40 29 19 32 17 31 19 22 19 24 32 31 33 33 24 23 27 22 27 23 32 22 34 20 17 21 19 21 32 20 20 39 53 32 29 29 22 26 18 16 21 21 24 19 25 26 25 27 26 21 27 12 22 15 22 17 21 14 22 25 22 21 21 20 36 13 15 23 15 18 16 14 26 29 37 15 25 21 18 19 27 19 22 24 22 23 18 25 23 24 24 31 16 17 20 20 29 13 20 22 30 25 27 27 20 16 25 22 17 31 31 31 33 18 20 24 28 33 33 20 27 22 31 26 28 31 23 21 14 23 18 26 23 29 21 28 17 21 29 31 23 28 20 25 20 25 26 19 24 20 24 25 22 14 19 17 18 21 17 24 18 18 19 27 17 24 21 19 20 22 28 23 29 32 34 27 28 26 23 25 18 24 15 15 18 26 24 14 26 22 24 16 10 12 21 15 24 24 24 20 15 20 18 15 29 23 11 19 13 13 25 11 16 20 14 12 17 10 17 11 15 12 20 14 19 13 16 13 10 17 27 11 18 17 16 28 19 15 17 14 25 13 8 
];
B = [
0 0 0
 1349763 1013242 336521
 1720220 1344455 375765
 1481282 1153590 327692
 1305309 1015113 290196
 834681 638975 195706
 1255879 1013744 242135
 1022641 814855 207786
 814972 656459 158513
 1361004 1117269 243735
 2113795 1791884 321911
 1018403 837739 180664
 2388712 1981947 406765
 870659 721135 149524
 649850 537959 111891
 1771719 1531253 240466
 742125 620951 121174
 631610 529838 101772
 1523984 1306638 217346
 386524 316638 69886
 581697 500247 81450
 378951 311363 67588
 352658 292162 60496
 729375 618586 110789
 2297427 1979123 318304
 582210 497334 84876
 832965 710737 122228
 2447144 2112786 334358
 482211 403787 78424
 1093399 935012 158387
 3182923 2738707 444216
 617450 530080 87370
 1083218 942264 140954
 2722076 2385003 337073
 1443341 1267174 176167
 1420265 1263899 156366
 3637359 3218329 419030
 2694380 2374776 319604
 1389024 1236770 152254
 4596680 4094870 501810
 2247349 1984380 262969
 961628 846276 115352
 5846557 5225829 620728
 1234749 1095116 139633
 797196 697849 99347
 9260356 8358194 902162
 1391931 1237483 154448
 1188797 1026802 161995
 14158837 12896585 1262252
 2550243 2281654 268589
 449061 386947 62114
 24184180 22084433 2099747
 2776803 2523001 253802
 580747 492752 87995
 392566 336829 55737
 3994952 3632751 362201
 464735 389971 74764
 388717 335935 52782
 472033 396279 75754
 357901 312358 45543
 91059567 84528251 6531316
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
428 1290 2 1
93 179 0 0
148 376 1 2
190 280 2 0
159 276 2 2
171 276 1011 54
2473 416 2838 271
30019 416 3840 718
187722 520 5089 1051
787994 608 6951 1721
1633473 693 8467 2360
3209101 923 11084 3776
5491563 1305 15132 5945
9083396 2215 26029 11376
13522160 3441 30427 16155
18607849 5938 33009 20325
22493062 9689 36495 26759
24149479 15884 42070 35949
21539081 24411 50771 48354
14632640 34712 62756 62710
6952692 46663 76900 77429
2070576 61943 92985 93539
354461 81920 109680 110342
138873 105712 127196 128651
150441 131285 147645 149760
170915 158521 169349 171717
193635 185789 193499 196133
216884 215065 218255 220765
240672 241122 242605 246809
264756 266770 265512 271094
286068 290990 287416 291838
304704 309941 305341 310182
317258 324620 319234 325411
325539 336147 329382 334032
330209 343240 334193 337925
333786 342635 334342 339127
328580 339673 331212 335132
324340 330985 326655 329125
319011 325896 320482 324610
315053 320574 315789 318987
314003 317243 314276 316990
315365 317400 314766 318625
321194 321942 319770 324119
327973 329669 328013 331303
339782 339937 337349 342143
351275 351896 348563 353982
361032 363658 360546 364112
369443 370416 368462 372928
374227 375748 372113 376992
375112 374783 371388 377007
366760 368858 365620 369510
352170 356733 352669 356604
334814 339504 334490 339117
312849 317310 315317 319298
289085 294942 290813 293014
263875 268390 265340 267448
238287 243071 239602 242335
215326 219835 216780 218978
195928 198935 196107 198348
178459 179505 178448 180940
165417 167996 165222 166849
157320 158822 157754 158327
145002 145659 145233 146510
136688 138026 136951 138903
131241 131642 130564 132088
129492 129643 129351 130834
128748 128430 128049 128677
132376 132815 130787 131800
128959 128466 128207 129674
126166 126641 125008 126550
122248 121839 122382 123046
118675 118610 119064 121001
113726 113967 113132 114455
105885 106282 106162 106800
95068 95281 94550 96108
85056 85230 84891 85531
71073 70629 70516 71144
52983 53468 52993 53222
42617 42417 42311 42897
31868 31475 31189 31466
18596 18593 18464 18677
10684 11079 11027 11090
550 610 560 557
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
