A = [
1244633 1670518 1791617 1078620 2160396 1312605 1329736 1902094 1611534 1913727 1317623 1418495 1800902 1460851 1504134 1332508 1492115 1453565 1436064 1409383 1316363 1514370 1414937 1378546 1434700 1312155 1325685 1360086 1436006 1376848 1351764 1426709 1383117 1260927 1228608 1350086 1497428 1294839 1406867 1490049 1273118 1240191 1179066 1301847 1200647 1219994 1258695 1192668 1233644 1144960 1125623 1206182 1151474 1186259 1143957 1109269 1161924 1067815 1078583 1053592 1053072 1086414 1045438 1067799 1041029 1015863 1050131 1004642 1030019 991963 1027828 1024888 963319 983603 952971 986554 1046966 1015626 1022537 1020499 990649 970531 948757 953176 925147 933898 918990 875953 865638 858571 857534 855913 842925 838438 834211 827955 816124 805527 796445 782737 782821 778043 780892 776662 763119 769437 754694 748687 744595 732615 734686 723033 719372 716591 705031 708209 705767 700682 701742 691022 690321 681849 680573 674089 668286 663960 656752 657665 650226 642526 638121 632087 632475 627127 622880 622676 614761 610978 605736 604625 603214 595284 590605 584912 581101 579961 573826 571451 568242 562745 558687 553513 549635 544390 543457 542843 538662 533515 531444 525939 517202 516346 516845 512182 510657 509302 507294 503243 496256 492219 489332 490095 485927 486985 481734 476805 477250 471390 470133 466308 463929 463321 456794 455478 452762 448271 446740 441938 440866 436822 427510 428140 423106 424345 418742 412621 412010 406883 400123 398378 392325 394577 388406 390918 385398 381951 381766 372483 369288 367741 368286 366348 361102 358186 358705 350426 345705 345337 340462 336174 336002 330533 329255 331272 321215 320227 316757 313696 315479 309093 308401 306760 304661 302862 299668 298145 295782 293799 291812 292078 287416 285612 283973 280956 280203 279710 277371 275940 272925 270254 269324 267521 266683 264332 261710 261344 258715 257814 257166 254360 251387 249414 249287 249756 246521 244565 244821 241083 240108 239094 238580 235450 236341 232881 232449 229324 229424 227424 225033 224791 222058 220543 220179 217656 217436 216617 213694 215116 211022 212822 213428 207898 207347 206166 204002 204547 204719 202137 203809 197726 197109 198241 194255 194190 191957 195128 189889 188800 187462 186492 185289 186139 186397 184236 180555 179161 179039 176838 176403 176181 175701 174815 173066 173764 170699 169348 167494 168097 165416 164990 164518 164868 163054 160921 160687 160891 158841 157011 156021 154917 154914 154281 154334 150851 152035 149435 149816 148876 146708 146693 145339 143970 144854 143228 143088 142071 141815 140511 139908 138831 138349 137568 137177 135334 136065 134754 133516 136146 131712 131980 131240 131302 131546 128518 128012 130650 126692 126127 124824 124385 131152 123159 126064 122625 121718 120206 119099 120474 118251 118698 119264 117628 116997 114256 115714 113728 114290 113696 112172 111955 111223 111392 109178 109410 109470 108521 108067 107652 106637 108811 105706 104731 103734 104037 104077 103120 101499 101675 103163 101291 101092 99727 99480 98574 97801 100472 97427 98727 97424 101373 97367 94993 95068 94314 94171 97579 93705 100160 91788 90804 91806 90461 90811 90379 89531 88588 88034 90195 86695 88432 86494 86878 85927 84937 86051 83956 83889 84489 82829 83596 82244 80629 83969 81391 81329 81610 79851 80041 79721 78485 81059 80737 77498 76838 78293 76855 77329 75948 78730 75736 76020 73850 77108 74707 73249 74879 73775 73065 72260 74879 74021 70370 70823 74527 70704 68729 69228 70571 69877 69837 68254 67717 67048 67729 67351 67658 68666 66405 65780 65532 64746 65279 64869 63683 67166 63239 64491 63196 62544 61695 63828 60847 63225 60084 60884 59552 60124 63046 58987 58432 58416 58494 59094 57027 56870 56953 56986 57217 56349 55695 56053 56126 54197 54817 54232 54343 54043 55794 54726 55371 52491 52518 52611 53602 53449 54786 51506 55936 51270 50789 50786 49678 50862 49528 49178 50560 49099 49963 48745 48482 48781 47816 47820 48226 47080 47054 47313 46626 46538 46775 47670 45907 46197 45680 46400 44792 45707 46728 48043 44271 44442 44625 43901 45090 45004 44096 47237 43117 42199 42102 42540 43058 44211 44050 41616 42552 43780 40411 40392 49693 40743 42711 39737 41054 40681 39667 39536 44062 39270 39116 37928 38425 38168 38258 38809 37422 37019 36565 37118 36284 36901 36204 36226 38652 35560 36407 34793 35345 35403 34989 34377 35171 33919 35529 34241 33667 34230 34867 35286 33062 32756 33051 32509 33391 34290 33030 33672 31789 31870 31380 32247 30950 31877 31143 31408 30832 30945 30149 30170 30045 31358 30118 29828 29746 29380 29578 29525 28847 29326 28527 28565 28453 28338 28542 27977 28286 28178 28652 28006 28297 27901 27533 28482 28107 27445 28878 26967 27774 27139 29365 26188 25964 26487 26829 27466 25944 29110 25913 24989 26668 25783 25629 26345 26618 25427 25273 24367 24269 26305 25338 26896 24069 23945 24762 25129 23806 25284 23524 23480 23123 23132 23009 22386 22840 23723 22965 22925 22204 22901 22437 22409 21824 22570 21257 21329 23396 22158 21745 21582 20957 22921 21252 21156 21249 20538 21059 21613 19772 20593 21716 20467 20328 19953 21020 21776 19159 19457 19550 19776 19397 19358 18601 19130 19482 20070 18615 18092 18129 19288 18199 18609 17755 18101 20034 17934 17798 17394 17241 17521 18081 17976 17086 17251 16520 17811 17782 17046 16700 16743 18247 17569 16816 17854 16777 17193 17114 16217 16392 16390 15800 16405 15437 16315 15557 16043 15748 15600 16460 15625 17903 14898 15184 15276 14861 14974 14724 14725 15693 14624 15366 14870 14705 14733 14117 16195 13797 13958 14244 13825 13822 13327 13510 13635 13447 13776 13413 12985 13241 12906 13058 12925 12743 12677 12786 12828 12459 12755 12639 12821 12292 12226 12436 12294 12208 12223 12303 12282 11917 11948 11992 11676 11845 12066 11561 11813 11297 11244 11426 11249 11449 11204 11401 10826 11406 10909 10981 11050 10757 10859 10914 10762 10645 10726 10702 10605 10358 10536 10668 10472 10535 10229 10274 10185 10284 9965 10455 10043 10003 10367 9839 10218 9781 9546 9603 9616 9837 9488 9878 9715 9405 9421 9110 9157 9061 8890 9415 9074 10160 8791 8930 8758 8590 9300 8930 8685 9072 8661 9235 9274 8481 8393 8600 8302 8307 8443 8475 8382 8084 8188 8074 8196 7827 7957 7982 8341 8063 7698 7803 7771 7708 8384 7723 7656 7655 7651 7528 7584 7580 8510 7305 7326 7442 7348 7476 7333 7059 7491 7197 7106 7288 7033 7037 7251 6879 7284 8448 6792 7142 6919 7342 7315 6711 6859 6454 6828 6730 6551 6516 7007 6594 6411 6229 6273 6385 6119 7201 6254 6379 6173 6282 6189 6162 6161 7541 6176 6280 5908 6013 6043 5882 6060 5802 6071 5913 5697 5851 5750 5893 5811 5558 5672 5779 5604 5936 5795 5527 5708 5479 5569 5521 5394 5328 5337 5467 6117 5329 5360 5143 5083 6254 5143 5380 5184 5251 7037 4989 5288 5162 5116 6124 5004 5247 4959 5147 5197 4973 5042 5019 4863 5047 4710 5072 4779 4568 5009 5459 4720 4659 4589 4486 4887 4381 4832 4677 4645 4471 4319 4419 4665 4414 4617 4267 4519 4418 4386 4518 4259 4306 4207 4360 4297 4325 4278 4186 4183 4130 4350 4249 3968 4005 4072 4084 3971 4059 4133 4116 4004 3990 4597 4101 3789 4068 4101 4101 3743 4107 3649 3715 3697 3881 4133 4106 3543 3674 3532 3678 3457 3509 3349 3492 3873 3393 4455 3405 3411 3513 3437 3325 3213 3658 3310 3375 3127 3102 3304 3363 3353 3404 3984 3976 4165 3308 3459 3382 3362 3133 3188 3117 3080 3049 3032 2936 3017 3209 3202 2998 3093 2819 2963 3183 2780 2990 2959 2870 3593 2956 2895 2870 2815 3242 2993 3127 2915 2671 2985 2818 3922 2678 2679 2577 2679 2548 3030 2721 2724 2481 2572 2804 2862 2455 2614 2554 2573 2472 2548 2494 2545 2450 3414 2514 2591 2525 2439 2486 3447 2486 2495 2281 2272 2406 2698 2336 2548 2360 2834 2749 2454 2493 2362 2362 2382 2337 2411 2296 4535 2193 2156 2196 2289 2213 3279 2164 2485 2281 2138 2302 2019 2223 2771 2213 2494 2088 2388 2134 2003 2132 2129 2085 2106 1995 2024 1902 1971 1936 1823 2002 1855 1971 2011 1884 2096 1969 1863 2027 1929 1914 1973 1858 1833 1887 1911 1852 1957 1766 1764 1886 1830 2327 1746 1857 2098 1769 2750 1831 1688 1843 1700 2242 1973 2033 1839 1684 1766 2182 1692 1733 2452 1898 3452 1757 1926 1581 1875 2514 3780 1716 1752 1708 1808 2001 1672 3297 1703 2668 1679 1638 1880 2567 2167 1595 1380 3646 2635 1650 1947 1436 2353 2111 1323 2533 3217 1435 2927 1479 2178 3680 1292 2620 2118 2283 3232 1562 3089 2293 1620 4203 2110 3062 1982 1681 2092 2409 1463 3626 1808 1285 1355 1599 1662 1684 1568 1499 1305 1148 1226 1129 1141 1234 1161 1185 1154 1122 1135 1207 1167 1110 1160 1112 1187 1151 1042 1157 1121 1065 1077 1134 1093 1033 1092 1101 1035 1015 973 1046 945 1043 978 1029 1262 1067 1063 1038 1030 998 1063 1015 1041 1031 1035 1073 1062 1005 988 939 944 924 952 959 817 941 901 949 906 891 942 907 957 906 898 904 951 862 897 850 846 866 841 931 825 801 806 843 890 835 821 860 770 841 853 864 861 806 787 780 776 779 794 794 766 792 811 772 706 737 703 757 839 725 822 703 766 754 805 711 786 779 785 763 730 714 744 727 737 736 729 642 708 736 737 781 709 633 662 687 713 658 643 696 618 660 755 594 675 625 695 696 651 640 714 661 649 604 633 722 654 588 672 653 624 617 566 568 595 597 588 516 640 567 586 567 575 540 552 589 545 580 599 519 544 557 621 552 538 566 509 521 538 506 529 553 473 593 522 543 510 457 531 550 505 522 462 463 477 471 565 497 463 500 483 436 497 525 491 460 422 458 423 503 440 521 452 501 448 435 486 389 473 461 465 455 441 441 487 458 456 400 442 435 421 448 438 426 427 418 442 420 424 402 392 461 410 384 425 377 439 360 398 390 356 406 364 377 342 367 355 380 427 357 377 365 333 356 361 390 377 371 328 308 333 354 374 319 352 351 344 306 343 354 332 336 280 306 335 331 313 306 300 342 312 327 323 336 291 310 302 319 278 281 345 276 293 301 286 269 261 280 288 303 248 274 262 280 283 262 287 296 284 288 250 269 269 260 271 217 254 217 258 270 219 281 249 275 249 292 244 216 225 254 268 228 244 269 249 236 233 258 244 240 225 192 218 221 240 232 206 252 242 209 231 226 213 225 227 237 186 210 224 212 236 216 231 222 214 241 227 224 189 179 192 197 204 229 209 209 191 206 201 188 192 183 185 207 181 196 176 201 227 168 208 165 187 190 174 193 203 203 198 183 184 159 179 198 196 192 186 170 184 180 161 180 157 167 176 169 176 134 161 161 183 168 173 163 158 168 146 140 150 157 157 167 141 147 154 132 155 131 160 152 145 159 143 143 169 128 110 147 149 141 145 111 154 134 141 129 116 124 144 153 136 129 151 143 127 126 145 139 111 151 150 140 129 124 124 135 146 114 112 141 127 123 132 121 174 132 146 117 124 113 150 134 111 144 123 113 110 127 117 150 124 137 113 114 137 95 128 93 118 123 104 105 129 106 122 103 122 147 133 121 106 104 106 116 110 114 120 115 104 91 85 116 115 113 101 113 92 117 92 103 99 130 108 85 120 101 127 94 89 90 81 84 80 96 108 80 106 84 90 96 94 95 113 89 115 106 71 76 91 99 103 75 79 79 90 84 85 90 62 66 94 61 95 100 94 101 96 72 75 90 77 90 99 103 80 77 65 78 63 80 90 79 
];
B = [
0 0 0
 367403 249039 118364
 639132 454306 184826
 525607 362523 163084
 488301 334995 153306
 434790 296180 138610
 386898 270366 116532
 320385 217328 103057
 293515 206941 86574
 276133 192206 83927
 473622 352748 120874
 332487 253140 79347
 346805 270647 76158
 354976 277518 77458
 351164 278433 72731
 445543 363581 81962
 409937 333485 76452
 426736 345709 81027
 409354 334747 74607
 433665 360557 73108
 464499 383091 81408
 432583 360752 71831
 437099 366114 70985
 451298 380177 71121
 446734 378110 68624
 506382 426059 80323
 475866 398334 77532
 521890 439467 82423
 466129 398816 67313
 502422 425485 76937
 527460 442984 84476
 546662 459876 86786
 551588 463986 87602
 513096 440063 73033
 682898 571999 110899
 529966 455611 74355
 550551 467126 83425
 1414598 1178507 236091
 536742 464233 72509
 670669 572945 97724
 1217597 1022594 195003
 661832 565813 96019
 1102763 932085 170678
 545736 472959 72777
 668900 572782 96118
 1137070 959205 177865
 667512 574516 92996
 1101500 932593 168907
 659187 568499 90688
 1050718 893160 157558
 660650 566791 93859
 1034140 879355 154785
 689174 593927 95247
 1034504 882363 152141
 673700 582955 90745
 1109376 941991 167385
 981767 841801 139966
 631983 550258 81725
 968804 831109 137695
 499749 440327 59422
 86376086 77911687 8464399
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
80 16 0 0
2 19 2 2
2 67 6 5
1 74 2 2
4 74 4 3
6 258 10 6
553 270 32 46
7351 450 70 70
105550 686 129 134
575642 1040 242 281
1236950 1623 419 417
2098448 2259 738 799
2763702 3427 1735 1767
3284519 5271 4397 4426
4121675 8389 9638 9657
8278118 22417 21682 21663
8308328 39388 46363 46721
6298344 64182 74297 74195
4091751 103298 103414 103670
639422 148607 142703 142254
223444 194682 181494 181440
241410 234433 225643 227687
261245 298409 272438 272849
299835 343241 315673 317376
329409 393876 354150 356030
357840 428754 384723 387253
379773 446993 405059 408466
395130 449070 413535 415019
398751 433678 408410 410613
389518 408467 391613 395228
372607 375398 369107 370874
346597 343113 340607 343682
321750 317268 317555 319577
302163 298960 299014 300649
291326 284515 286013 287311
284825 279255 279633 281034
281855 275783 277260 278288
282424 277759 278652 280482
289038 282339 285334 286151
298656 293675 294044 296090
313061 305424 306592 307880
329508 322284 324684 326609
352319 344848 345972 346655
374742 365408 368779 370449
399229 389064 393084 395298
421831 414513 417079 416888
440938 434367 436235 437923
455978 449956 450604 453122
464290 459006 461345 462615
466121 460202 461089 464228
456616 452728 453065 455836
436893 433595 434412 436790
411620 408609 409380 410121
380114 379270 379334 380562
342614 342814 342626 343594
304688 305990 306267 307536
269566 269825 269184 270551
236340 236978 235999 236399
206691 206727 206630 208371
183293 182054 181885 183212
163920 164092 163707 163153
150899 152102 151152 151314
141312 142380 140591 142381
135939 135630 135204 135971
131520 131938 131159 131986
131121 132149 131228 131760
133194 132413 133216 133851
137665 137688 137012 137190
142908 143059 142673 143113
150021 150439 149710 150811
157363 157516 156694 157519
161133 161850 160623 163349
160376 159967 160449 160823
147909 146912 147569 147565
128977 128914 128178 128842
106955 107050 107238 107570
82415 82531 81789 82570
59242 59017 59010 59169
45863 45436 45758 45664
30739 31015 30829 30915
18335 18727 18509 18582
7963 7834 7890 7967
426 373 475 417
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
