A = [
337672 586242 3282687 436565 718585 548828 542320 621210 626512 572911 562690 591432 563150 558919 588290 569629 558000 580828 559335 558091 578206 551358 549834 571619 555207 581575 613342 602941 619117 657070 641135 634720 658187 640974 627646 660709 636024 622664 647893 635420 613434 644956 623880 607932 636205 610718 604710 628871 602399 596347 611604 594640 581373 601624 578462 567888 588706 568340 553019 575139 552847 542618 562812 539102 535631 545909 528560 516375 535328 513929 502301 520446 506415 493153 504648 492662 475299 492663 477213 469426 477973 470801 452848 467406 450517 444428 454028 443509 427669 441710 428101 423151 432958 417362 408966 423958 407042 400787 410510 397068 391447 397961 387095 381312 387782 378469 368102 376833 365522 361015 365594 355606 351030 355180 349886 340318 347105 337853 329905 339161 330376 322159 330712 319173 312899 324137 312039 306351 314827 305138 299112 305752 298603 294331 297276 291585 285946 292320 286791 281523 283410 276740 272501 280309 271102 267360 270825 265463 258565 263892 259374 255911 260029 251868 249868 253753 247365 244802 250742 240920 239603 241492 236121 231261 236412 229630 226447 232674 225401 220463 229083 218950 216822 222048 214533 213824 216831 209978 207995 212876 204702 203932 204959 201110 200296 200368 197936 196211 195236 193225 192037 193408 190411 186303 190714 185272 182932 185498 180591 180518 184277 178057 177024 179055 176303 173447 175446 171857 170464 170877 169546 166178 169906 165018 164854 165217 159870 160013 163736 159755 156892 159067 154319 154644 155995 153460 151499 153219 150278 148073 149494 147048 146977 146186 144463 143919 144254 141665 141669 141324 138955 137474 140118 137610 135654 137869 134672 133878 135781 134925 130779 132142 130647 128883 131260 126293 126403 129624 123985 122921 125724 124801 123019 124298 121289 120661 121051 120240 118774 119045 118044 115454 115522 114976 112596 114630 111096 110743 112512 110809 110008 110027 108927 108129 108662 106637 105183 105590 105847 103605 104479 102693 102782 103473 101417 101569 103277 100427 99917 100668 98586 97205 99447 96735 97262 96771 95401 94005 95134 94685 93086 95347 92271 93291 93234 91299 90504 90793 89816 88711 90177 88839 87205 88778 86687 85757 86629 85855 84466 85918 83013 83237 83953 83201 81401 83489 82283 81980 82092 81456 80828 80399 78193 78480 78021 76600 78048 77802 76091 76030 76295 74372 74155 75554 73926 73254 74165 72638 72152 73759 72790 71415 71760 72066 71687 69691 70389 68995 70528 68974 69454 69051 68819 67251 68509 68369 66974 67800 66048 66691 66204 65561 64684 65724 64111 64280 65227 63210 62770 63916 61710 62646 62325 61561 61169 61966 60900 59819 61464 60124 58831 61143 58968 58165 58708 58315 58022 58851 57331 57373 57865 56835 56127 58136 56870 56655 56552 55533 55384 56158 53518 54733 54657 54153 53547 53369 52161 52533 52523 52660 51045 51672 51122 49368 51598 50784 50068 50360 49631 49430 49406 48978 48838 49581 49246 48454 48411 48341 47559 48875 47715 47983 47627 47112 46359 47208 47022 46281 47108 45310 45544 45913 44706 43818 45895 45131 43965 44912 44345 44247 45207 44333 43395 42877 43278 43092 42965 42474 43026 41933 41781 42004 40168 41677 40270 40292 40727 39332 39061 40403 38918 39119 39035 38567 39106 37827 38257 38596 38189 37678 38790 37382 37658 37686 37168 37488 37223 36692 36902 36945 36611 36213 36813 36266 35485 36640 36055 35711 35097 35313 35760 35348 34456 34508 33878 34937 33524 33923 33167 32607 32881 33153 32222 32628 32011 32177 32160 31690 31653 32107 32159 31240 31336 31615 30607 30398 30293 30449 31420 30372 29187 29769 30082 29259 30166 29262 29479 29547 28850 28771 29057 28479 28623 28257 28439 28936 27599 27974 27712 27721 27835 27751 27403 26818 27748 26805 27143 27288 26980 26429 26555 26600 26612 26405 26288 26171 25715 25771 25488 25280 26497 25114 25611 86232 25345 24707 23744 23797 24523 24168 24022 24068 22769 24567 23667 23824 23671 22996 23577 23447 23122 23447 23004 22694 22564 22996 22510 22702 22729 21512 22200 22155 21629 21843 21412 21568 21281 21246 20969 21355 21151 21041 20767 20478 20211 20618 20192 19969 20226 20031 20056 19689 19444 19513 19309 19577 18861 19351 19153 18943 19141 18752 19011 18674 19009 18543 19019 17614 18253 18183 18218 17825 18211 17506 18283 17276 17753 17848 18361 16760 18421 17560 17071 17589 17813 17140 17531 18216 17132 17301 17363 16637 17414 16632 16693 16551 16647 16133 16468 15877 17247 16360 15814 16433 15743 16245 15649 15908 15782 15626 15540 15822 15531 15179 15160 15720 15163 15196 14981 14742 15024 14674 14883 14567 14262 14596 14834 14133 14221 14538 14027 14306 13762 14064 13993 14245 13785 13866 13820 13943 13103 13556 13353 13513 13191 12978 13219 12987 12861 12982 12920 12584 12973 12658 12801 12766 12628 12034 12760 13025 12001 12605 12329 12015 12095 12143 12008 12172 11950 11440 12096 11738 11302 11536 11507 11334 11330 11384 11401 11141 11073 10896 10783 11018 10579 11091 10719 10900 10776 10575 10205 10619 10885 10749 10539 10381 10472 10585 10137 10070 10047 10150 10115 10147 9736 10063 9664 9815 9960 9525 9587 9788 10086 9904 9768 9661 9625 9910 9528 9304 9572 9706 9372 9349 9416 9122 9274 9212 9148 9315 8886 8996 8839 9068 8770 9088 8985 8850 9185 9384 8639 8733 8972 8506 8475 8793 8614 8778 8457 8336 8528 8153 8165 8201 8317 8286 7892 8579 7759 8362 7886 7958 8365 8162 8444 7983 8001 8086 7850 8194 7787 7819 7723 8009 7681 8044 7407 7390 7496 7512 7583 7421 7693 7615 7431 7435 7087 7387 7281 7063 7285 7124 7173 7039 6965 7061 7002 7162 6996 6754 6732 6692 6588 6836 6826 7238 6735 6684 6695 6801 6930 6860 6470 6464 7036 6675 6529 6619 6592 6451 6412 6503 6521 6483 6909 6571 6299 7379 6022 7088 6334 6729 6051 6579 6010 6144 5950 6308 5815 6035 6044 5988 6306 5891 5921 5615 6255 6015 5937 5893 5860 5523 5582 5775 5563 5719 6020 6744 5715 5609 6899 6000 5853 5591 5408 5446 5405 5542 5468 5400 5351 5595 5509 5460 5340 5555 5058 5449 4928 5186 5247 5346 4969 5676 5154 5035 4887 5248 5032 4951 5095 4890 5167 4886 4841 4992 4817 4840 5059 4975 4881 4878 4603 4536 4991 5169 4649 4838 4627 4734 4811 4560 5099 4358 4658 4513 4655 4487 4465 4501 4674 4542 4477 4730 4425 4646 4510 4368 4182 4416 4317 4414 4483 4277 4297 4184 4472 4188 4582 4664 4230 4379 4491 4180 4196 3998 4303 4169 4110 4079 3747 3885 4046 4245 4068 3900 3902 4117 3971 3865 3933 4013 4159 3977 3830 3850 3961 3961 3916 3547 3585 3983 3888 3878 3803 3744 3932 3881 3696 3761 3787 3669 3634 3898 3931 3694 3863 3787 3772 3680 3635 3764 3683 3644 3510 4008 3541 3716 3606 3651 3388 3591 3622 3455 3412 3426 3394 3505 3380 3693 3427 3475 3243 3482 3418 3302 3385 3430 3384 3325 3465 3217 3159 3311 3072 3296 3238 3092 3324 3339 3108 3383 3190 3218 3173 3379 3142 3255 3029 3274 3290 3136 3093 3108 2904 3136 3146 3231 3063 2981 3084 3011 3005 3038 2943 2946 3173 2981 2930 3067 2685 2976 3036 2704 2930 2695 2725 2592 2954 2987 2874 2828 2778 2975 2625 2767 2786 2889 2583 2549 2638 2685 2780 2754 2798 2692 2603 2668 2612 2550 2649 2491 2610 2520 2838 2712 2576 2590 2609 2527 2660 2602 2549 2611 2573 2576 2463 2602 2537 2466 2478 2608 2204 2605 2543 2384 2458 2393 2458 2414 2405 2293 2374 2263 2487 2340 2245 2444 2295 2542 2334 2451 2398 2148 2182 2193 2181 2211 2089 2283 2107 2150 2306 2110 2207 2206 2207 2087 2482 2046 2362 2276 2052 2093 2071 2221 2130 2180 2002 2160 1935 2001 2002 2045 2012 1936 1924 2011 1853 2013 1879 1961 1896 1916 2452 1762 1837 2011 1839 1851 1805 1916 1875 1822 1880 1911 1850 1909 1703 1868 1872 1892 1719 1806 1567 1721 1624 1707 1724 1697 1772 1676 1823 1743 1761 1656 1755 1767 1695 1809 1676 1644 1817 1673 1919 1646 1695 1891 1805 1614 1748 1791 1682 1682 1634 1787 1658 1654 1477 1651 1504 1520 1642 1727 1488 1735 1559 1471 1608 1564 1589 1714 1645 1479 1629 1550 1459 1544 1493 1510 1573 1511 1539 1602 1504 1543 1691 1377 1435 1554 1478 1384 1580 1662 1402 1307 1502 1628 1365 1427 1397 1416 1411 1458 1264 1486 1291 1497 1366 1397 1398 1360 1336 1370 1386 1278 1331 1403 1321 1308 1363 1218 1332 1434 1185 1284 1355 1238 1270 1337 1318 1138 1295 1231 1454 1134 1088 1191 1303 1229 1181 1208 1233 1370 1319 1166 1262 973 1240 1283 1229 1198 1182 1121 1159 1140 1109 1149 1172 1044 1199 1015 1107 1160 1154 1299 1224 1021 1154 1259 1047 1015 1163 1117 1131 1069 1014 1139 979 882 952 1118 909 969 1085 970 1045 951 963 1026 977 1023 1037 1192 1057 1161 999 1033 1053 988 1212 1144 1025 987 1127 1162 1119 1022 1121 1024 923 995 1015 990 972 991 1000 878 915 972 1023 984 929 882 982 880 1005 914 831 1026 912 846 979 749 825 894 859 896 775 741 849 837 963 819 816 886 755 825 984 807 763 1033 732 939 850 807 882 802 893 824 801 876 790 942 809 826 852 898 894 849 747 742 863 702 776 736 790 880 659 763 723 788 678 789 791 734 671 678 840 643 776 776 719 875 663 799 788 738 722 827 722 784 753 844 709 769 750 742 695 665 765 701 739 701 728 724 653 780 605 747 624 723 645 652 614 614 626 639 599 693 658 681 650 597 689 597 788 598 647 642 532 691 583 567 691 742 590 609 714 614 684 584 624 628 617 663 622 684 659 642 651 615 674 743 571 628 628 642 549 581 632 550 596 545 581 578 557 583 530 654 494 595 517 588 514 539 735 553 561 587 596 595 492 692 542 606 580 509 607 661 525 606 599 527 508 530 529 561 575 621 567 581 564 532 584 538 616 576 516 524 491 505 493 576 562 631 389 472 494 446 530 492 531 438 497 439 427 532 534 467 485 466 460 545 447 422 421 466 462 419 388 459 505 390 426 398 431 418 451 491 378 459 424 454 524 529 399 451 441 465 418 419 429 497 416 452 434 485 457 419 451 479 470 429 409 345 488 354 333 394 377 372 415 377 362 446 410 347 394 440 322 411 379 341 406 350 431 347 397 388 327 434 347 388 410 462 363 405 409 399 358 393 420 417 337 386 382 386 362 353 447 390 342 396 388 406 388 317 354 401 352 370 336 358 341 319 364 430 356 467 331 409 359 353 526 371 435 390 427 392 393 387 380 342 478 338 374 368 372 374 467 471 391 340 362 404 458 421 418 324 438 374 384 353 353 314 364 359 350 398 316 303 342 367 368 352 399 350 343 319 365 368 324 355 364 299 481 329 407 429 388 352 434 265 413 302 417 384 432 353 403 388 375 394 497 287 376 372 416 367 465 383 439 510 408 340 353 289 380 341 299 338 324 298 285 256 301 321 312 253 274 305 308 229 359 301 307 299 287 346 297 265 281 284 308 289 333 292 417 321 321 225 350 325 353 328 299 306 331 313 312 341 244 277 335 324 285 317 278 284 224 312 275 298 384 308 379 355 392 295 375 333 302 340 329 333 382 237 290 267 269 244 360 241 318 299 290 271 242 299 284 329 311 273 315 244 315 240 259 277 268 271 279 249 225 314 231 343 183 318 
];
B = [
0 0 0
 79400 4908 74492
 48013 3606 44407
 132536 26317 106219
 103175 3087 100088
 37102 2912 34190
 44829 3911 40918
 46654 5343 41311
 36915 4245 32670
 112026 25678 86348
 27997 3066 24931
 30215 3808 26407
 29631 4241 25390
 51542 7859 43683
 24510 3743 20767
 115341 28689 86652
 23991 3752 20239
 25920 4163 21757
 29641 4916 24725
 52459 9693 42766
 19044 3463 15581
 127127 31113 96014
 27857 5033 22824
 24198 4654 19544
 59642 11098 48544
 73675 16168 57507
 23798 4415 19383
 315600 80219 235381
 12553 2904 9649
 28585 6162 22423
 22327 5117 17210
 39590 9573 30017
 15445 3017 12428
 175516 48170 127346
 11293 2546 8747
 28347 6651 21696
 20125 4702 15423
 36161 9451 26710
 7466 1440 6026
 221745 60018 161727
 323 97 226
 664 174 490
 5719 1070 4649
 32262 8443 23819
 4940 1153 3787
 4797 1142 3655
 7377 1455 5922
 18675 3606 15069
 368250 100327 267923
 473 124 349
 5629 1385 4244
 5561 1337 4224
 7039 1495 5544
 22678 4617 18061
 434218 119913 314305
 12076 3190 8886
 9694 2465 7229
 12874 3830 9044
 314022 84473 229549
 78288 22339 55949
 57234140 19372631 37861509
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
302 942 1 0
274 239 0 0
587 389 2 0
471 495 0 0
164 518 5 3
140 767 289 34
4571 1138 882 286
24834 1369 1618 986
93566 1865 2702 2034
257514 2655 4657 3879
460344 3412 6505 5781
766367 5073 9209 8643
1123167 7104 11989 11944
1577810 10488 15840 15937
1911467 14362 21354 21059
2092670 20802 27014 27221
1860817 27286 33560 33839
1290248 34434 41231 41241
641218 44312 51716 51565
260060 56710 63506 63339
144832 67863 74921 74626
135840 77715 86502 86094
137911 89428 96228 95786
135745 97593 103070 102170
137023 101618 105771 104914
132456 107338 106290 104543
126579 112541 105947 103877
127227 128601 105050 104701
138018 176731 107951 107793
146334 209078 111111 110367
135458 148172 115577 113013
121299 177402 111823 111390
95400 177385 90415 88884
71827 113107 68784 68580
52917 67948 49453 50580
39633 43701 36002 36644
25515 28662 26106 25794
16212 18184 17820 17528
11893 12761 11939 12109
8683 8768 9059 9044
6549 6327 6416 6175
3933 4253 4209 4453
784 831 985 1015
522 441 526 483
398 375 373 370
172 173 169 184
103 116 103 106
26 22 28 21
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
