A = [
5318706 4987564 75693210 3893027 4121839 3882738 3780393 4319918 4157957 4129820 4271341 4334312 4531393 4647509 4668324 4747813 4891925 4997594 5037693 4987985 4971571 5032965 4995515 4856490 4818968 5335763 5293035 5224018 5625352 4673224 4643453 4570189 3648896 3663708 3627855 3618161 3593907 3505767 3505482 3519220 3473604 3493597 3494870 3464640 3513775 3435163 3399384 3520227 3424803 3426307 3433944 3280033 3315394 3289472 3187372 3113918 3137318 3183314 3054938 2999990 3032339 2979600 2937406 2873221 2830193 2823659 2754134 2702583 2692568 2641079 2617672 2617314 2580663 2567351 2575087 2538789 2512453 2503089 2448926 2401677 2382920 2371231 2314401 2278786 2290601 2217843 2155493 2070395 2016576 2000963 1971657 1937003 1932386 1897676 1875463 1857665 1835332 1817581 1792730 1771320 1755250 1736660 1712237 1697638 1681124 1662619 1646239 1625392 1612430 1598944 1577598 1577497 1567110 1553074 1551526 1537162 1751433 1756654 1753714 1967179 2014119 2018195 2012086 2026762 2019536 2003950 1986409 1964051 1939397 1918387 1894548 1871098 1847856 1825742 1803058 1782312 1758015 1739939 1716722 1691085 1669937 1648925 1631504 1611133 1586202 1567713 1549896 1525845 1505141 1484858 1461954 1444140 1426476 1402578 1385264 1363948 1343788 1327931 1307365 1289396 1270586 1253157 1231823 1214842 1199069 1181434 1169589 1148955 1136176 1119614 1104343 1089133 1077907 1061948 1049280 1031504 1019178 1007101 989376 976835 961806 946907 936383 923001 913560 901855 884933 876904 863265 852215 841807 828370 819438 807631 794770 783826 774194 764412 753665 740431 733204 723668 711904 702058 693912 684636 676242 666768 657334 647601 635352 628029 616870 607029 600082 592251 583547 576616 569104 562899 555832 547750 539955 531209 522498 513079 503294 494722 484255 476552 467480 459461 452156 444473 436166 430806 423514 417691 409670 404379 397447 391257 385648 379561 373918 368599 362029 356224 351928 344956 341324 334791 330365 324729 319559 314597 310305 305115 299238 296696 291500 286848 283290 278929 274671 269940 266516 261655 257287 253989 250583 247152 243705 239630 235363 232380 228432 224424 221858 219359 215587 211962 208505 205631 202732 199255 196506 194229 191128 186906 185245 182479 178920 176908 174062 170452 168821 166104 163427 160667 158771 156224 154763 151949 149165 146877 145020 142672 140150 138041 136538 134306 132184 130421 128375 126221 124129 122169 120255 119052 117268 114742 114445 111581 110150 109149 106132 105047 103663 101799 100399 98722 97602 96561 93807 92707 91184 90421 89040 87004 85824 84669 83241 82276 80944 79523 79025 77285 76036 75033 73299 72519 71391 70537 69360 68282 67394 66204 64852 64874 63248 62558 61402 59924 59305 59165 57766 56913 55907 54940 54177 53280 52803 51624 50640 50090 49183 48655 47703 47067 46453 45547 45134 44751 43315 42842 42490 41601 41099 40389 39811 39215 38474 38212 37139 36750 36053 35740 34865 34864 34136 33375 32900 32585 31950 31759 30946 30241 30110 29655 29163 28539 27973 27846 27189 27343 26487 26338 25763 25175 24903 24621 24305 23857 23460 23453 23010 22610 21961 21777 21482 21279 20646 20490 20035 20015 19455 19305 18789 18717 18195 17955 17808 17531 17321 16922 16823 16363 16147 16052 15715 15448 15416 15087 14787 14502 14464 14210 14017 13829 13250 13261 13014 12875 12727 12412 12102 12107 11879 11665 11463 11515 11339 10926 10750 10789 10674 10365 10216 10290 9871 9873 9618 9323 9514 9058 8861 9255 8721 8769 8520 8472 8235 8154 8225 7998 7893 7985 7640 7532 7357 7215 7013 6984 6910 7035 6895 6687 6549 6487 6251 6557 6170 6039 6046 6087 5661 5624 5668 5574 5413 5292 5386 5179 5188 5088 5045 4955 4933 4621 4679 4477 4683 4447 4478 4195 4288 4177 4101 4061 3947 4052 3885 3851 3811 3906 3690 3694 3760 3522 3488 3449 3467 3231 3321 3276 3213 3016 3190 3170 2981 2998 2946 2953 2887 2805 2813 2834 2850 2787 2628 2603 2680 2627 2544 2483 2470 2466 2410 2406 2311 2294 2308 2274 2209 2198 2157 2104 2005 2054 2012 2038 2099 2135 1994 1999 1898 1859 1852 1836 1822 1797 1787 1771 1678 1686 1602 1765 1625 1631 1626 1592 1587 1577 1541 1583 1516 1446 1486 1495 1477 1384 1448 1396 1345 1341 1342 1304 1281 1304 1267 1294 1241 1232 1270 1212 1220 1205 1181 1169 1159 1212 1131 1083 1103 996 1139 1058 1062 1104 1091 1062 1041 1032 1053 992 948 1070 942 962 938 1002 895 946 996 912 920 934 897 850 854 888 840 812 790 840 822 820 835 829 790 795 852 758 773 777 816 758 756 760 752 716 739 691 663 733 729 720 614 680 655 663 698 682 651 624 614 623 630 597 624 618 617 570 584 596 612 573 602 633 581 571 564 583 584 536 531 542 567 522 539 591 562 546 542 524 549 523 481 513 523 454 535 480 437 521 491 522 514 500 520 462 458 461 469 488 424 471 458 429 405 421 386 422 418 431 439 415 401 428 428 417 432 410 381 392 390 372 407 355 403 372 378 404 423 407 374 362 353 372 394 346 343 361 346 315 369 359 321 380 362 373 345 336 360 329 338 366 324 338 382 277 332 324 319 370 331 322 298 359 343 311 336 302 275 316 319 291 332 307 304 295 261 300 319 293 289 313 276 278 269 285 257 263 245 273 277 286 283 300 272 266 286 254 236 277 265 238 288 267 296 248 265 243 251 220 230 240 257 221 242 220 230 229 234 240 259 231 217 242 209 263 237 207 223 234 210 225 214 191 191 216 230 200 194 239 236 223 199 214 210 207 207 190 203 211 177 197 190 198 210 181 197 170 198 199 212 180 203 198 190 208 188 205 193 184 207 191 204 196 185 183 184 194 188 180 172 183 176 189 185 178 167 179 169 153 189 214 181 164 157 164 160 172 156 146 183 144 160 167 152 148 164 161 159 134 181 142 159 177 156 174 143 177 164 146 148 159 152 152 136 169 151 137 162 130 158 146 141 137 144 140 162 163 153 145 146 156 138 139 150 133 155 125 145 129 160 130 141 133 135 145 147 127 120 138 114 150 135 136 110 135 112 110 124 132 113 132 129 139 117 117 131 115 120 108 130 124 115 121 134 117 136 121 108 131 150 135 151 154 181 224 239 385 563 582 658 722 635 695 755 774 755 780 864 572 448 490 459 538 472 453 441 428 425 417 442 448 450 464 482 465 463 495 481 460 434 433 466 469 484 481 467 492 442 451 451 482 495 485 548 538 482 564 574 718 648 637 686 653 661 686 643 628 647 1787 776 631 578 548 439 471 499 345 322 348 305 318 340 282 248 297 301 252 212 282 234 234 252 204 190 237 202 197 228 202 232 213 206 221 229 226 219 253 292 293 308 553 494 1649 1308 1360 771 711 621 648 594 499 378 324 257 228 245 263 237 217 220 200 211 155 158 149 187 422 2313 207 166 123 114 100 108 120 72 100 75 81 85 59 70 83 78 94 69 85 92 75 91 84 89 90 101 87 104 109 96 96 118 117 132 106 117 135 149 150 127 151 131 114 102 124 125 160 158 157 152 146 184 164 151 160 206 184 207 204 197 208 174 186 214 213 213 251 198 213 272 246 246 224 212 228 213 226 217 277 270 235 250 249 226 251 288 271 233 269 271 264 255 289 284 282 274 297 340 384 345 331 347 378 305 346 318 341 315 318 323 337 327 359 343 338 339 368 339 355 360 343 370 352 333 399 381 418 377 382 394 345 331 310 288 349 329 312 350 350 220 254 219 188 149 135 244 148 194 211 207 401 201 395 660 298 212 161 133 109 114 151 136 124 134 184 146 153 113 111 125 129 134 125 155 149 162 124 147 141 103 117 132 172 164 165 158 174 149 198 184 171 166 173 199 153 168 173 134 149 148 144 130 124 153 158 153 143 147 159 148 150 165 164 145 148 146 162 142 145 140 188 165 171 162 129 121 136 122 108 105 110 94 117 529 146 133 126 89 85 103 93 55 72 70 79 76 66 83 74 86 75 72 75 64 59 64 57 62 54 51 65 53 45 45 40 35 32 40 41 50 46 56 40 35 49 38 50 43 28 40 33 41 50 52 44 33 46 38 53 46 45 42 45 44 60 42 36 28 43 63 41 21 55 43 55 58 40 44 41 36 37 34 28 36 21 18 23 22 28 22 32 23 24 25 20 25 24 28 24 25 31 23 20 26 38 34 34 31 28 42 42 25 24 30 52 28 28 48 44 30 36 37 44 44 31 48 34 47 47 35 38 49 52 43 59 46 45 57 62 30 51 58 53 79 50 50 43 74 69 55 70 66 50 55 58 63 56 68 49 61 60 65 60 61 61 72 82 68 74 92 76 90 54 78 70 70 84 78 74 68 57 77 83 67 68 70 81 76 40 70 62 76 60 63 51 70 65 66 63 57 64 59 81 52 53 59 52 62 57 49 51 59 54 59 50 48 54 57 60 55 56 51 75 70 57 40 46 63 55 41 36 39 36 22 22 27 25 21 25 20 15 8 23 15 20 15 17 22 11 13 23 8 10 21 14 13 14 11 18 10 17 14 11 13 15 12 11 19 16 14 16 16 13 11 12 22 15 16 16 13 17 11 8 14 15 20 17 11 11 5 12 13 14 19 14 12 19 15 10 9 19 11 11 8 11 11 11 17 11 16 15 12 16 9 10 13 12 15 11 12 19 12 9 12 12 14 10 13 8 13 18 5 5 15 8 15 8 17 11 10 13 5 7 11 12 3 15 14 10 15 10 11 16 17 15 16 13 10 10 11 15 8 10 12 11 13 8 10 11 16 10 10 14 12 14 4 10 8 6 14 13 13 9 9 13 8 12 13 9 8 14 19 11 9 8 15 10 19 5 10 13 7 8 6 10 7 7 6 11 9 7 12 10 11 7 5 13 6 11 13 6 8 13 6 11 10 6 15 5 12 9 10 8 7 11 33 9 6 11 10 11 12 6 12 14 5 12 11 10 13 12 6 13 21 13 12 11 14 15 13 9 9 12 17 17 18 10 11 13 14 10 13 11 16 16 8 15 18 15 9 10 12 8 8 4 26 14 11 8 5 9 9 10 12 7 10 10 12 18 8 6 13 8 14 9 9 11 6 14 13 16 8 11 15 13 11 10 8 19 17 11 10 8 9 10 8 9 13 11 4 15 11 13 8 7 9 8 10 8 13 8 8 10 4 8 13 12 5 10 3 8 9 9 8 8 8 8 6 10 4 5 7 4 7 3 9 6 10 6 7 9 11 4 7 8 7 8 8 5 7 13 5 9 10 10 
];
B = [
0 0 0
 1063244 687857 375387
 2232120 1702001 530119
 1323624 943943 379681
 1146586 813205 333381
 980733 687236 293497
 779045 555377 223668
 717734 514437 203297
 742337 553566 188771
 771402 574591 196811
 1730847 1416989 313858
 1011591 779082 232509
 976687 749853 226834
 952972 731695 221277
 907104 700979 206125
 1364248 1115815 248433
 1066976 844904 222072
 1078988 859198 219790
 989725 788225 201500
 1056206 831390 224816
 1356355 1109975 246380
 1172990 936722 236268
 1171735 944091 227644
 1184581 946843 237738
 1143887 915995 227892
 1392049 1136647 255402
 1184069 947364 236705
 1295967 1038936 257031
 1191524 954088 237436
 1244536 1002754 241782
 1342424 1098456 243968
 1295208 1052655 242553
 1278713 1039762 238951
 1231718 1007355 224363
 1451727 1179993 271734
 1318379 1086839 231540
 1305414 1057427 247987
 2656726 2144453 512273
 1242992 1023705 219287
 1451983 1185441 266542
 2369382 1928782 440600
 1401538 1151139 250399
 2169650 1765446 404204
 1235567 1024080 211487
 1387573 1141157 246416
 2215716 1810897 404819
 1407185 1160652 246533
 2126361 1738208 388153
 1381679 1147259 234420
 2041976 1669342 372634
 1389926 1157624 232302
 2012376 1649048 363328
 1442948 1199742 243206
 1989419 1630994 358425
 1364432 1138222 226210
 2096507 1720582 375925
 1880655 1547308 333347
 1294004 1086579 207425
 1898556 1564719 333837
 1081252 919992 161260
 239686485 221270616 18415869
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
258 470 4 3
47 66 1 2
72 252 2 1
110 147 9 2
110 155 1 5
142 150 10 2
216 217 20 14
649 252 27 16
264984 292 53 19
1997431 381 109 33
3986973 513 232 74
7947344 545 447 191
14287104 758 3477 1196
23442155 1145 13790 5201
30694693 1909 14216 7852
33660328 4311 16785 12189
29122302 9783 27263 24581
21733220 17657 43080 41608
13812511 27951 63616 63092
6708030 41173 86332 86459
2304537 58050 107137 108709
580881 80086 130515 130816
201551 109774 155917 156034
189846 146473 184176 184251
218352 187966 214624 216262
251263 231994 248790 251422
287848 276655 286868 287869
326835 321760 326471 328386
366137 364879 366732 368580
402632 407089 405340 408757
436791 444569 440671 442940
468182 477347 469600 473185
493208 502439 493221 496904
508508 518787 511068 513033
516516 529966 520299 523818
524681 531669 524283 528853
522640 531678 524656 528981
520118 530601 521598 527214
521554 527856 523206 524479
521165 526890 521401 525415
526786 531825 527467 528862
535463 540858 536012 539438
553045 555137 551242 555301
576079 576523 573139 578030
601668 602788 598522 602988
631216 631606 628878 633780
660709 662348 658367 663237
686534 688789 686597 689426
710684 712156 710299 714651
725776 728593 726142 729084
730467 733796 730830 732266
722185 725725 722382 725735
703657 704594 700231 703994
669367 674213 670728 673539
629403 632991 631179 634964
582971 585381 580158 585645
527746 531100 528681 531708
475087 477139 475941 477372
423252 425870 423007 425823
380571 380264 379276 382056
341115 343539 340788 343487
306355 306731 304655 306058
282679 281948 282594 284405
267722 267911 267102 268406
256583 257207 257390 259066
253159 253781 252537 253996
264719 264297 263925 265353
306042 305777 304565 304408
282330 281994 281822 283351
292872 293603 291714 295178
275548 278632 277214 278539
250657 251991 252316 253609
264331 265938 264400 265388
183322 183495 183375 183984
155223 154922 155204 155966
127056 126616 125791 126194
103167 103702 103127 104605
89923 89097 88903 89444
75883 76037 75462 75857
61577 61378 61080 61269
38974 39201 39361 39485
21643 21564 21946 21736
1069 1188 1142 1124
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
