A = [
1899250 1933045 8539162 1953514 1984666 1872456 1847308 1865924 1860355 1818415 1863965 1966785 2055458 2189640 2398954 2535321 2658473 2830038 2854883 2846826 2877275 2826966 2784826 2776816 2795867 3346608 3366591 3405154 3911914 3460936 3500594 3465982 3052982 3109167 3066174 3067331 3050923 2991426 2980953 2946287 2937900 2926432 2948390 2943765 2940889 2962267 2917289 2896838 2877826 2823602 2805009 2797875 2788675 2778913 2767708 2757519 2747964 2728784 2710225 2691261 2670866 2655401 2640552 2630697 2618884 2599995 2587083 2570793 2557813 2536684 2514862 2497823 2473107 2458171 2441589 2423282 2409832 2398343 2366643 2341884 2324976 2306120 2286845 2266600 2247358 2231508 2217013 2192220 2174028 2153994 2131543 2112054 2094042 2074559 2060839 2045004 2023733 2007107 1992206 1974800 1952145 1930099 1912878 1895864 1880078 1863997 1847239 1829564 1813214 1796143 1776250 1756152 1744728 1724689 1708520 1695076 1680123 1662140 1650063 1631231 1615300 1598846 1579239 1564806 1544203 1529338 1517957 1499966 1486958 1470053 1457043 1441512 1425440 1407230 1392240 1377853 1366721 1350873 1335052 1321054 1306286 1290849 1280572 1265779 1252417 1239622 1225473 1213400 1198510 1184686 1172527 1159989 1147000 1138792 1117832 1107715 1096321 1082728 1067997 1057190 1047052 1035153 1023012 1009926 998588 984573 974972 963130 951562 942590 928015 918118 908818 898260 884601 873373 861116 853599 841043 832145 821121 809415 800850 790126 782279 772231 760841 751827 742280 731987 724255 717071 706745 698660 691453 681229 675863 666651 656805 649436 641470 632519 622134 615573 607019 599434 593450 583382 576766 569936 562904 556197 549023 539706 533589 528535 520505 513288 505662 500070 492605 487309 480829 473671 467246 460439 454555 449505 442309 434793 429832 424593 418712 412618 405125 402376 397728 392213 386906 380773 374345 372872 366589 361521 356979 350922 347492 341201 338652 333353 329248 325017 320709 315636 310911 306225 301283 299012 294080 289340 285514 280643 277160 274295 270282 266529 263096 259635 256797 253210 250913 246232 243713 241576 237246 233204 229977 228833 223238 221327 218642 215191 212355 208370 206682 203456 199891 197770 198522 192966 190986 187583 184645 182239 178621 177391 174225 172314 169949 169443 165160 162042 160270 158829 156179 154000 152338 150177 147575 144977 143287 140791 140254 138902 136392 134247 131680 129643 126592 124896 125862 121749 119966 118060 118102 115440 113701 110942 110370 108268 107387 106288 103631 102894 101698 99573 98780 97192 95656 94115 93521 92722 91671 90686 89474 88232 86202 84646 84651 82892 81408 81527 79158 77112 75878 75716 79322 72913 74410 71195 71613 69233 69039 68131 66633 65376 64922 64826 62790 62320 62179 60217 59733 59234 57968 57782 57335 56718 56580 55449 54214 53397 52751 52400 53478 52390 51205 51032 50166 50135 49678 48986 48755 47960 47070 46080 43153 42717 42366 41982 41524 40897 40269 39990 39357 39022 38941 38066 37614 36910 36772 36290 36287 35531 35206 34601 34260 34041 33054 32483 33261 32727 31978 31534 31030 30782 30460 30027 29924 29232 28680 29013 28400 28071 27732 27193 27071 26811 26464 26216 25466 25034 25163 24770 24570 24267 24079 23977 23790 23219 23067 23243 23180 22755 22623 22349 21918 21968 21582 21334 20589 20570 20593 20321 20183 19858 19779 19708 19289 19191 18874 18540 18856 18362 18233 18228 17801 17705 18006 17387 17405 17150 17012 17031 17067 16885 16605 16530 16135 16442 16382 16007 15721 15778 15898 15655 15226 15553 14869 14572 14816 14609 14765 14800 14566 14571 14540 14326 14224 14290 14201 14148 13942 13875 14054 14087 13666 13816 13502 13282 13664 13363 13510 13351 13183 13188 13266 12902 12950 12482 12458 12654 12690 12224 12361 12006 12242 11897 12048 11910 11611 11659 11625 11716 11607 11648 11384 11671 11773 11423 11203 11148 11048 11032 11016 10918 10825 10792 11022 10721 10602 10913 10808 10650 10507 12362 10123 10039 10189 10048 10366 9987 10063 9609 9733 9665 9587 9516 9318 9376 9677 9609 9574 9439 9582 9424 9457 9278 9135 9048 9333 9239 9180 9156 8889 9046 8912 8838 8998 8984 8543 8830 8639 8517 8458 8654 8558 8689 8480 8503 8346 8297 8282 8111 7876 8075 8026 7888 7827 7698 7682 7735 7546 7550 7827 7568 7388 7485 7377 7413 7239 7421 7369 7243 7275 7240 7198 7302 7013 7176 7175 6999 6935 6985 6839 7014 7067 6883 6793 6476 6668 6613 6344 6419 6404 6566 6419 6489 6240 6249 6298 6286 6291 6133 6071 6088 6759 6020 6071 5950 5844 5757 5729 5758 5795 5783 5775 5776 5676 5668 5706 5642 5723 5543 5654 5706 5471 5503 5448 5437 5346 5399 5542 5453 5438 5435 5304 5212 5325 5398 5370 5191 5184 5230 5298 5205 5385 5176 5313 5223 5394 5333 5442 5400 5479 5526 5533 5657 5558 5453 5390 5295 5338 5291 5337 5404 5382 5217 5224 5245 5319 5291 5059 5485 5152 4954 5238 5222 5209 5353 4970 5144 5165 5019 4944 5009 4679 4702 4471 4609 4856 4775 4582 4604 4648 4772 4542 4665 4617 4345 4388 4258 4415 4502 4421 4263 4322 4226 4135 4254 4300 4220 4183 4156 4244 4305 4244 3975 3980 4094 4091 3980 3935 4134 4005 4103 4080 4015 3846 3823 3871 3944 3824 3834 3908 3755 3823 3668 3642 3703 3621 3494 3669 3559 3655 3474 3388 3388 3505 3430 3475 3506 3456 3484 3501 3358 3375 3542 3504 3447 3338 3323 3326 3238 3397 3384 3312 3224 3329 3246 3243 3296 3302 3192 3263 4038 3452 3381 3413 3325 3403 3332 3319 3272 3152 3047 3193 3050 3051 3037 3115 3152 3178 2995 2846 3272 2926 2879 2719 2789 2821 2642 2698 2647 2761 2689 2729 2676 2802 2763 2665 2658 2619 2667 2649 2611 2591 2576 2595 2514 2622 2719 2489 2542 2403 2498 2484 2403 2537 2541 2404 2343 2419 2353 2401 2303 2363 2499 2229 2371 2244 2349 2290 2366 2178 2276 2360 2281 2158 2160 2169 2215 2158 2111 2140 2130 2148 2192 2157 2243 2315 2191 2105 2171 2112 2008 2102 2100 1981 2090 2040 1830 1854 1946 1979 1835 1867 1791 1821 1912 1984 1981 1849 1968 1859 1878 1897 1873 1895 1824 1785 1837 1844 1799 1813 1774 1782 1780 1782 1758 1856 1838 1801 1790 1749 1701 1829 1831 1754 1737 1700 1803 1722 1660 1664 1665 1635 1639 1708 1685 1773 1791 1667 1751 1754 1707 1562 1619 1606 1612 1553 1572 1558 1673 1567 1532 1558 1511 1489 1521 1623 1498 1513 1550 1513 1479 1483 1527 1505 1665 1598 1627 1484 1512 1490 1483 1374 1413 1505 1541 1506 1456 1428 1468 1424 1457 1437 1399 1358 1391 1431 1356 1413 1355 1328 1344 1278 1357 1412 1373 1408 1379 1384 1343 1305 1319 1437 1461 1454 1437 1367 1467 1333 1356 1326 1413 1399 1361 1389 1357 1267 1386 1295 1196 1221 1338 1285 1345 1297 1428 1246 1261 1265 1293 1205 1262 1304 1274 1217 1287 1226 1324 1303 1215 1218 1249 1147 1246 1198 1144 1271 1231 1225 1191 1217 1262 1256 1216 1183 1179 1177 1149 1139 1156 1194 1143 1206 1075 1149 1145 1186 1112 1119 1082 1157 1162 1215 1152 1087 1099 1046 1026 1066 1141 1171 1084 1097 1101 1111 1093 1067 1051 1149 1083 1080 1061 1135 1074 1021 993 1070 1009 1051 1043 997 1010 1058 985 981 1016 929 936 954 1035 1005 962 949 1030 1002 1018 994 943 926 900 973 997 999 1026 1018 1098 1034 1040 1027 1036 1035 1022 1106 1102 1180 1040 1014 1092 1055 1073 1031 1015 1050 1125 1128 1063 1038 1039 1039 932 974 895 883 930 853 897 890 887 900 998 914 870 828 860 892 915 871 831 907 815 805 800 767 849 788 750 775 768 801 776 791 806 835 814 853 855 863 856 835 873 679 693 663 630 669 646 623 646 682 674 659 688 630 677 681 615 627 643 700 767 675 663 711 661 660 665 687 643 699 666 712 664 588 661 650 685 726 735 728 686 647 718 694 691 701 752 726 632 610 625 609 645 607 608 613 629 662 632 614 600 583 635 639 605 607 631 638 610 598 599 664 536 541 552 571 593 556 581 576 580 509 552 514 539 519 537 520 507 548 525 492 526 515 505 510 542 482 516 524 488 462 543 544 535 488 476 487 549 498 499 479 523 512 513 486 511 574 490 534 551 554 574 577 591 509 509 478 556 456 478 478 482 479 451 445 432 443 407 393 443 485 521 473 558 503 495 438 531 513 526 528 519 475 544 535 511 509 509 497 513 546 506 496 547 570 505 534 519 539 534 537 522 528 520 581 525 616 510 528 550 617 568 612 560 636 596 584 585 590 597 548 517 517 556 527 594 523 502 504 550 493 506 458 501 519 416 439 421 380 425 411 403 446 415 416 376 417 408 406 406 406 416 424 424 394 376 392 387 443 395 394 403 411 376 377 385 351 360 366 377 362 397 359 375 312 333 373 320 333 304 363 365 362 361 323 332 363 336 317 345 330 352 362 327 343 361 334 305 312 341 329 333 340 304 295 467 339 332 323 326 343 316 327 270 323 302 310 300 353 301 306 302 308 317 307 314 312 328 307 257 294 328 340 315 317 307 287 320 314 316 299 328 300 290 281 294 307 307 347 352 321 373 355 394 379 355 399 383 379 350 389 377 427 351 387 384 402 369 343 342 336 397 344 329 329 367 329 330 311 294 302 330 340 323 315 323 345 339 333 337 353 317 323 327 313 325 302 299 315 314 319 334 292 293 311 328 309 296 295 290 323 334 385 338 327 305 332 335 290 328 288 337 333 330 345 316 331 354 337 343 371 377 380 401 399 409 495 479 450 433 391 415 438 426 426 411 419 390 413 405 411 397 361 378 393 394 398 319 362 323 356 347 324 359 367 341 336 318 350 394 379 330 359 374 435 362 382 350 325 286 306 301 247 277 247 248 233 274 276 249 277 274 256 262 255 243 233 236 261 276 288 272 266 279 236 310 264 313 288 277 363 300 345 291 288 344 327 295 296 314 286 282 280 280 261 265 238 257 294 264 250 253 246 258 249 284 230 263 272 238 282 238 246 189 212 273 250 263 223 209 203 180 186 209 208 221 199 206 214 194 216 216 232 201 194 205 207 217 205 218 212 178 195 183 203 198 210 208 202 203 162 170 201 176 158 183 181 209 199 199 180 164 186 179 179 178 181 194 189 185 180 147 183 204 217 184 190 156 199 157 189 178 189 140 174 181 215 205 206 198 197 204 194 184 196 213 182 155 189 192 186 182 179 179 194 176 166 174 178 157 175 167 183 171 174 190 176 173 154 232 189 188 194 179 171 165 186 170 207 162 185 175 171 175 180 191 171 176 188 159 178 202 169 162 194 174 179 177 193 194 206 177 178 192 172 193 182 159 170 172 157 158 201 183 197 220 178 158 209 182 192 182 203 166 209 182 175 174 184 179 169 189 173 190 180 194 166 172 161 167 198 174 184 187 182 167 167 166 167 147 168 168 167 170 164 197 164 168 167 166 181 152 180 140 172 169 166 153 164 151 164 174 170 191 175 159 192 190 179 153 172 180 163 138 146 170 160 164 163 154 159 162 147 184 151 156 157 162 169 161 159 177 155 184 170 148 175 187 163 148 144 147 156 164 158 137 
];
B = [
0 0 0
 1484881 308112 1176769
 1508847 323427 1185420
 1615733 332548 1283185
 2389503 529078 1860425
 1421246 306840 1114406
 5417953 1378082 4039871
 2220627 522408 1698219
 1373115 349975 1023140
 1341270 363031 978239
 1002666 253496 749170
 727748 181169 546579
 496843 133010 363833
 394701 108835 285866
 801373 210916 590457
 717080 184970 532110
 657820 168498 489322
 1903237 528197 1375040
 1251496 319875 931621
 1131751 305041 826710
 851330 234744 616586
 989571 294962 694609
 971675 298179 673496
 757254 233188 524066
 940687 297168 643519
 765122 241123 523999
 1414338 438329 976009
 1187934 373682 814252
 954815 308785 646030
 1197138 397548 799590
 996969 338980 657989
 1249146 431507 817639
 1238366 440259 798107
 1180600 425026 755574
 1534058 552938 981120
 1367111 499785 867326
 1576032 581536 994496
 2937363 1027048 1910315
 1502291 563958 938333
 1739576 657204 1082372
 2815194 996379 1818815
 1705739 650055 1055684
 2698083 972515 1725568
 1592139 610541 981598
 1786305 693804 1092501
 2726667 994440 1732227
 1868977 729386 1139591
 2657857 980974 1676883
 1877159 747198 1129961
 2642194 995887 1646307
 1742519 702320 1040199
 2944585 1118837 1825748
 1700166 698589 1001577
 2851090 1094646 1756444
 1595598 659112 936486
 3014677 1178878 1835799
 2967151 1179062 1788089
 1687396 715344 972052
 2936457 1170263 1766194
 1435780 627211 808569
 122978119 55580005 67398114
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
181 372 3 4
100 54 0 5
177 103 3 1
179 116 3 3
152 125 4 3
218 178 11 13
682 297 25 16
5808 403 40 29
64443 502 128 63
494698 801 226 165
1353036 1063 356 250
2587048 1886 574 493
3898814 3156 909 734
5650485 6745 1481 1327
7342026 13882 2286 2078
9099799 29113 3714 3434
9664794 54465 5754 5595
8471851 87217 8502 8297
5666256 122888 12038 11689
2405242 157383 15472 15144
543440 188177 18753 18895
91682 213659 22424 22519
52829 221837 25438 25137
47661 201700 27392 27199
43304 163073 28836 28642
41673 123770 29244 29681
41212 90810 30075 30470
38443 69696 30791 30575
38081 57120 31444 31447
36644 49631 33296 33066
36998 45745 34537 34670
40454 45318 35428 36258
45259 47518 36967 37306
49321 49336 39640 39781
50765 50598 42803 42812
51722 51782 46264 46039
56394 55369 50095 50759
61537 60196 55818 55862
63985 63693 61597 61315
68478 68448 66755 66906
76238 77806 74482 75204
84595 84947 84410 83727
95071 95302 94531 94589
106844 107365 107148 107029
121621 122112 121301 121539
138912 140197 139292 141782
157578 159068 159507 158538
174466 175426 175024 175507
195694 196261 196121 195334
218649 217647 215989 215362
238692 237186 237254 237823
255618 256245 255680 256521
274274 275161 272222 272314
289768 290939 289963 290232
310879 309693 310708 309872
319360 320290 320133 319560
335443 337523 335438 334988
348894 348938 347655 347043
354761 354755 354233 353681
362409 364213 363516 364221
377429 378874 374339 375769
369305 366109 364538 367483
346760 346286 347655 348523
299068 300777 300642 302742
223771 225228 226400 223207
138615 138772 137830 137817
83053 85967 82828 85136
71900 71357 69922 68952
73289 70652 68741 69470
60915 63091 65423 59114
46462 47924 44673 48767
34963 32448 31319 34358
1954 2314 2044 1711
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
