A = [
1321647 1764389 1930826 1132851 2301025 1427588 1374900 2034679 1908282 2124839 1361314 1641209 2034918 1554135 1631269 1469709 1625222 1573902 1552548 1490704 1431521 1617596 1507162 1494162 1528744 1444239 1442530 1483466 1571163 1452217 1520753 1560819 1476145 1389715 1333411 1489245 1509846 1383222 1487991 1503527 1387959 1325157 1288944 1407214 1291921 1322971 1338160 1286031 1322808 1230016 1200239 1277407 1226430 1250588 1211661 1201942 1238167 1141324 1177930 1127151 1123921 1161737 1109652 1137819 1113542 1082357 1123671 1097414 1125594 1076479 1114799 1121923 1038724 1060368 1033838 1064706 1095865 1046084 1092144 1096534 1038262 1049067 1019181 1046866 1017183 1011791 1029319 982976 967844 961776 957687 956452 946325 938102 939128 930889 916950 910965 901803 889320 888435 881766 885054 882474 869626 868237 854477 845569 836962 831249 825954 817320 814736 809130 800089 801337 794340 791895 786570 777676 772409 762445 757449 752657 746872 745208 741321 730357 727680 719787 715468 710498 706065 701610 694810 686975 683509 678026 675058 668367 661955 659751 651710 647763 641129 636585 633466 627242 625876 620388 613815 608177 601404 595347 594456 589643 586376 581089 577052 574218 565233 560060 563581 555450 553825 551306 543943 542083 532546 528702 525183 523907 519597 516354 510359 507873 504303 498618 495575 490891 485615 483221 477824 473698 468797 464828 463435 459374 456805 452271 445288 445890 438967 436926 429986 424956 425441 419611 414672 409981 405555 404286 400784 399468 395807 392725 390893 384593 379390 376851 375385 373591 370215 365866 365417 358878 354979 351561 346888 344210 341243 338478 335581 331804 328394 326931 323645 321234 320507 315871 315098 312160 309490 306897 304775 301512 299368 297873 294600 292984 291462 289719 288277 284930 283217 281138 277897 276628 274349 272238 271119 268375 266818 262968 262337 260694 258561 256822 255684 253349 251292 249054 249174 245838 243939 242878 241807 239105 237665 235541 233935 232596 230637 228769 227087 224778 223897 221677 219623 218671 217049 216334 213809 211717 210853 210215 207899 204735 204255 202470 201901 199511 198313 198246 195742 195193 192979 191799 188502 188237 187132 185402 184281 183545 182076 179785 178681 177909 176364 175058 173688 171900 170478 170115 167932 167369 165858 165587 163265 161867 160877 159184 159907 158073 156237 155445 153489 153082 152584 150729 150450 149002 147168 147304 145516 145311 144337 141597 142034 140865 140111 139015 138496 135225 136450 134085 134693 132968 133066 130968 130070 129351 128409 127867 127287 126566 125977 124043 123488 124006 121697 121170 120643 120367 119652 117713 116861 116505 115079 114941 114195 114153 112116 112053 111495 110751 110009 108524 107861 106998 106848 106732 105967 105176 104225 102968 103278 101983 101658 101178 99561 99103 99083 97383 98592 96840 96214 95818 95395 94337 94242 93515 93296 91967 90673 91010 90352 90069 90113 88103 88293 87501 86697 87230 85964 86274 83949 85213 84548 83457 83038 83262 81283 82031 80434 80809 80269 79174 78496 78641 79159 77835 76971 76991 76293 76210 75156 75488 75147 73666 73679 73851 73136 72430 71638 71471 71358 71198 69484 70070 69258 68694 68965 68410 67741 67431 67192 67468 66420 65457 66151 65185 64809 64297 64596 63872 63365 63303 62707 62439 61578 61624 60621 60364 60043 60529 59801 59605 58604 58872 58481 57963 58178 57213 57533 56598 56570 55899 56172 55817 55966 54764 55120 54115 54318 53647 53044 53163 52926 52826 52592 52182 51767 51687 51220 50978 51112 50647 50158 50087 49946 50018 48508 48292 49045 48001 47623 47659 47308 46879 46714 46393 46283 46407 45501 45270 45017 45216 44590 45012 43938 44585 43955 43497 43301 42818 42691 42697 42383 42375 41860 41206 40535 40709 41080 41095 40765 40401 39785 39859 39206 39594 39069 38878 38922 38182 38701 38088 38078 37989 36950 37240 37216 37329 37631 36663 37019 36610 35840 35831 35336 35683 35821 34913 35435 34480 34724 34634 34517 34116 33398 33841 33687 33567 33998 32656 33015 32771 32554 32319 32468 32065 32051 31703 32042 31606 31355 31478 31392 30527 30491 30500 30804 30391 30347 29850 30378 29950 29333 29647 29013 29155 28961 28885 29021 28337 28782 28140 27846 28138 27641 27512 27096 27591 27479 26795 27479 26928 27056 26615 26257 25858 26269 26615 25556 25676 25761 26060 25167 25366 24579 25431 24935 24709 24498 24728 24472 24087 23863 24234 24049 24002 24042 23276 23925 23353 23477 22715 23618 22615 23078 22655 22421 22633 22641 22235 22206 21742 23370 21666 22219 21468 21652 21421 21289 21643 20837 21345 21326 21051 20721 20892 20353 20507 20138 20407 20398 20585 19944 20202 19482 19870 19400 19632 19107 19433 19370 19258 19245 19212 18899 18766 18798 18706 18591 18341 18906 18972 18310 18332 17598 17929 18113 17923 17803 17815 17477 17444 17425 17373 17219 16946 16897 16667 16916 16924 16788 16853 16435 16021 16301 16103 16102 15937 15862 15938 16078 15836 15431 15420 15283 15360 15563 15350 15175 15354 15054 16248 15043 15003 14847 15414 14647 14636 14764 15023 14923 14634 14389 14419 14379 14433 14062 13901 13923 13838 13844 13520 13839 13588 13722 13462 13299 13223 13057 12733 13141 12845 13189 13056 12793 12688 12810 12843 13088 12569 12656 12374 12129 12772 12301 12309 12070 11933 12314 11880 11951 12736 11847 11891 11801 11497 11938 11584 12134 11695 11191 11516 11093 11396 11013 11177 11025 10933 11002 11029 10852 10872 10685 10745 10953 10821 10469 10698 10434 10253 10428 10527 10255 10428 10058 10170 10205 10112 10021 10051 9913 10015 9922 10016 9779 9653 9804 9563 9655 9630 9523 9523 9503 9521 9184 9420 9206 9307 9201 9236 9075 9037 8997 8756 8818 9024 8884 8920 8792 8864 8839 8568 8535 8433 8783 8560 8335 9355 8200 8560 8144 8075 8172 8396 8112 8176 7982 7968 7787 7820 7829 7801 7779 7810 7962 7564 7555 7750 7473 7597 7466 7378 7828 7423 7528 7215 7216 7323 7054 7284 7207 6986 7178 6957 7457 6844 6874 6772 6889 8609 6934 6937 6658 6703 6872 6573 7021 6893 6502 6629 6628 6548 6321 6475 6542 6124 6277 6086 6433 6284 6112 6073 6348 6036 6130 6124 6057 5943 5838 6023 6273 5812 6051 5736 5899 5755 5701 5797 5797 5828 5684 5617 5613 5491 5589 5591 5525 5496 5566 6084 5504 5495 5411 5279 5135 5376 5480 5152 5152 5001 5358 5092 5047 5071 4996 5090 5017 4892 5205 4938 4967 4928 5010 4926 4768 4945 4801 4743 4832 4821 4915 4961 4613 4836 4690 4641 4745 4755 4460 4665 4364 5175 4572 4543 4333 4466 4287 4520 4407 4360 4270 4296 4295 4191 4143 4352 4012 4096 4199 4226 4152 4148 4050 4082 4009 3948 3957 4040 4127 3990 4049 3789 3821 3980 3953 3877 3830 3880 3769 3821 3734 3757 3666 3767 3618 3729 3780 3677 3645 3665 3563 3543 3634 3602 3441 3685 3488 3389 3502 3386 3577 3301 3289 3310 3340 3392 3433 3323 3369 3254 3330 3242 3204 3237 3135 3175 3210 3286 3215 3152 3066 3080 2964 3065 3150 3048 2988 3104 3057 2973 2862 3089 2921 3019 3006 2850 3012 3067 2953 3111 2961 2886 3139 2750 2833 2939 2689 2965 2766 2718 2853 2633 2794 2698 2868 2758 2705 2780 2665 2637 2644 2579 2738 2539 2518 2536 2520 2581 2549 2515 2409 2561 2494 2522 2436 2361 2487 2458 2326 2505 2467 2355 2316 2443 2326 2357 2282 2223 2338 2270 2448 2315 2250 2232 2226 2227 2183 2154 2279 2236 2243 2169 2144 2101 2220 2059 2095 2096 2132 2127 2031 2136 2056 2079 1957 2065 1963 2058 2041 1974 2036 2016 1967 1997 1852 1958 1915 1909 1981 1922 2066 1999 1953 1889 1840 1917 1854 1895 1881 1921 1838 1892 1855 1858 1842 1829 1744 1772 1838 1790 1711 1741 1701 1741 1653 1811 1755 1694 1676 1685 1754 1706 1571 1694 1638 1533 1593 1557 1674 1718 1644 1553 1542 1494 1730 1640 1628 1539 1674 1511 1557 1466 1541 1537 1514 1529 1483 1478 1532 1426 1424 1399 1466 1432 1454 1435 1442 1416 1430 1415 1443 1377 1486 1363 1400 1337 1360 1374 1336 1263 1361 1270 1428 1444 1348 1343 1168 1293 1320 1163 1393 1262 1274 1207 1263 1232 1203 1264 1293 1248 1150 1194 1205 1151 1079 1211 1129 1178 1152 1227 1135 1137 1135 1141 1078 1111 1124 1137 1154 1039 1096 1090 1101 1197 1075 1191 1038 1057 1102 1071 1125 1091 1097 1054 1038 1070 980 1070 1011 1032 1079 1100 1053 1024 995 1094 956 1018 961 958 937 962 968 1005 943 1035 980 941 892 911 907 978 910 983 970 949 944 932 927 942 873 866 857 998 950 895 887 896 862 878 855 940 899 827 849 776 910 798 754 836 813 803 800 795 807 797 851 790 782 791 766 849 791 798 768 800 800 793 802 817 733 763 759 768 747 791 685 754 709 749 754 720 764 731 684 736 682 756 727 730 693 685 678 666 646 684 705 704 698 705 701 695 675 608 727 589 711 732 640 691 602 663 601 636 616 590 695 551 579 589 649 622 582 610 592 533 643 641 572 609 525 603 543 642 545 599 545 578 532 601 544 595 551 515 587 522 518 522 555 570 587 553 509 494 469 514 504 523 559 500 518 492 517 487 544 507 539 473 473 412 488 502 516 507 469 491 437 440 463 466 450 501 455 455 484 465 445 443 494 488 398 421 509 429 452 447 412 526 440 445 435 409 434 417 405 436 430 429 425 368 428 409 448 403 381 418 366 421 388 383 389 384 416 397 408 392 352 450 355 378 382 382 422 383 363 391 315 373 356 367 335 357 372 339 305 341 328 380 347 369 355 353 335 325 297 362 366 353 347 368 316 357 346 360 296 299 363 323 330 340 321 315 272 298 293 327 336 307 304 298 297 282 316 275 290 287 278 282 333 285 334 278 294 303 290 276 317 280 264 247 293 305 272 269 264 293 232 260 294 289 257 276 258 248 246 255 242 258 241 248 226 239 241 244 251 238 267 212 236 248 233 220 224 237 220 272 205 227 202 237 244 222 223 249 230 228 215 256 209 221 202 228 201 226 214 194 214 190 188 237 195 213 233 214 213 212 273 176 238 200 210 182 193 203 207 211 192 197 194 183 202 171 175 223 184 193 169 216 182 199 188 195 176 181 172 181 169 149 180 170 167 152 158 168 144 173 156 160 171 171 147 159 165 148 138 144 163 164 174 147 152 160 152 177 145 163 153 178 145 140 162 139 147 148 154 174 147 145 134 155 140 159 160 152 143 120 140 135 126 135 145 155 144 117 126 121 124 134 143 132 143 112 136 153 119 150 139 128 136 136 139 125 98 132 141 123 127 103 115 136 138 113 132 125 119 107 114 132 128 122 116 116 112 126 120 121 117 131 117 104 114 127 125 131 108 113 119 97 99 127 121 118 109 111 109 104 97 115 97 103 101 114 123 103 103 98 109 121 91 108 94 92 110 103 104 87 107 105 118 96 83 117 93 88 115 114 100 82 98 94 96 105 94 80 96 89 108 82 90 96 97 96 85 117 125 95 106 86 85 77 113 97 99 82 87 95 89 92 111 90 86 78 84 88 98 89 82 88 76 104 97 75 74 89 92 89 89 88 86 83 74 84 94 109 98 86 67 79 78 99 84 86 65 85 82 84 90 81 66 68 80 74 90 85 85 61 73 57 70 78 61 74 73 64 68 59 70 67 88 51 72 76 85 42 73 60 67 64 86 70 67 73 68 72 64 97 55 65 58 57 52 56 66 75 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 746903 538534 208369
 465266 303495 161771
 796042 569118 226924
 741399 531802 209597
 1008923 714623 294300
 511226 340969 170257
 844270 600674 243596
 1281693 787407 494286
 782795 560658 222137
 642298 403057 239241
 1173158 751896 421262
 963684 678105 285579
 1169950 737331 432619
 547554 367369 180185
 887661 615694 271967
 1192933 756182 436751
 650354 421987 228367
 1210074 782426 427648
 921082 641554 279528
 1201548 780996 420552
 648030 425974 222056
 1178390 767453 410937
 945152 651450 293702
 1201800 782256 419544
 630457 405462 224995
 1292386 842363 450023
 1157933 758865 399068
 605241 389128 216113
 1179852 771957 407895
 748608 536799 211809
 99081025 71873297 27207728
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
6418 319 1 0
1 578 0 0
3 1802 0 0
5 2459 0 0
5 2298 2 0
72 9421 17 12
10694 8103 81 104
52530 14023 263 236
149966 22374 520 547
389608 33464 1036 996
790732 51433 1467 1549
1655936 67409 2337 2335
2880134 98694 3126 3084
4792827 141067 4203 4319
7066054 199085 5349 5235
9654438 268790 6411 6804
11129208 338149 7582 7742
10819917 412284 8905 9103
8901603 494447 10797 10540
5908849 563229 12503 12516
3048467 616963 14902 14769
1154824 659856 18402 18082
299162 692099 22162 22155
61254 702527 25821 25506
28641 703270 28842 29176
28144 684829 31419 31566
29830 644852 34082 34021
30700 574218 35478 35375
32543 472365 36444 36247
33444 356322 37002 37052
34267 246976 37576 37397
35765 163375 38610 38519
38277 109622 40290 39964
41774 80113 42823 43259
46602 68127 48194 47439
52277 65849 53525 53394
59249 69305 59597 59463
65723 74120 66670 66453
74052 81532 75191 74674
82654 89182 82608 83326
92415 97954 92665 91928
101434 107404 102104 101515
111791 117980 112719 112047
118914 125655 119262 119268
124025 130002 124888 124521
128187 135191 129611 128873
128888 135001 128811 128814
124540 131119 125478 125311
118004 123788 118861 118709
108429 113486 109247 109240
94703 99613 96036 95630
81240 84264 81882 81485
66268 68857 66467 66692
53341 55446 53756 53847
41347 42719 42187 41557
32240 33029 32258 32026
24686 25539 24979 24960
19602 20173 19821 19864
16026 16346 16365 16410
13957 14012 13893 13880
12641 12992 12996 12821
12435 12468 12389 12524
12622 12616 12492 12611
13243 13146 13141 13267
14616 14389 14439 14275
15892 16217 16110 15936
18312 18002 18149 18084
20893 20892 20705 20739
23674 23746 23702 23876
27184 27415 27261 27025
31018 30761 30797 30643
34938 34987 34916 34878
38531 38825 38996 38780
42201 42416 42586 42180
44220 44215 44673 44146
46445 46556 46714 46441
46679 47031 46513 46487
44543 44426 44996 44876
42390 42125 41781 42223
33627 33466 33652 33473
21947 21850 21830 21810
10006 10028 10027 10031
498 482 519 507
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
