A = [
458557 457803 2788309 147402 144600 137077 134742 139512 146331 153677 196756 230161 250647 305072 345888 352653 349962 348748 342114 336223 328762 320812 313735 312363 325356 429138 442491 470121 569346 512168 525561 518956 470197 486948 477761 481423 475972 463428 461556 455098 455002 452515 455494 461356 459521 464127 452298 447497 439992 426617 422527 419355 422824 421891 421981 423387 420704 418635 418807 413829 409203 410857 409286 407211 408477 406279 403617 404808 401296 396867 395081 389323 387047 386042 382287 379619 379301 377309 373339 371703 368351 361448 362730 359258 353333 353160 351553 347748 345867 341876 337442 334721 328858 325218 324903 322158 317895 317305 312501 306884 305976 301884 297951 294972 292474 288522 286517 284058 280707 278891 274084 270084 266819 262634 259740 258181 254047 251353 249575 246603 245770 244322 237966 235781 232328 228020 227588 224293 221898 219060 216252 214090 211374 207973 203777 201608 200098 198288 195212 193930 191349 187925 186997 184164 180707 179357 176104 173139 172594 169762 168226 167365 164501 162559 160244 157906 156255 153852 152438 150258 149189 146861 145189 143732 141744 138713 137882 135867 134177 133378 131082 129248 128021 126511 124777 123822 120470 119747 117405 115413 113834 113106 112142 110054 109229 107455 105578 104382 102333 101111 100463 98824 96981 97812 94776 92849 92434 91163 90084 88415 88496 86540 85609 84499 82092 82127 80660 79118 78757 77302 76265 76113 74021 73465 73292 71642 70150 69033 68382 67494 66410 65961 65120 64108 62925 62462 61857 60106 58796 59107 57453 57582 56589 56046 55617 54164 53979 53410 52353 51677 50479 50271 49278 48909 48408 47610 47159 46927 45856 44931 44752 43934 43258 42942 42268 41970 41391 40570 40313 40421 38825 38114 37762 38014 36873 36482 35682 35529 36050 34469 33825 33173 33599 32506 31914 31682 31101 31050 30958 30235 29897 29534 28640 28349 27971 27532 26933 26505 26250 25891 25581 24873 24867 24310 24043 23782 23482 22822 22413 22468 22267 21857 21294 21030 20894 20721 20499 20057 19778 19526 19516 19159 18519 18429 18134 18139 17477 17650 17464 17272 17032 17336 16407 16032 15733 15321 15354 15099 15270 14966 14722 14416 14282 14345 14030 13650 13420 13204 13327 12837 12587 12578 12452 12575 11921 11966 11953 11322 11414 11530 11413 11188 10802 10606 10497 10456 10147 10029 9785 9558 9530 9572 9648 9333 9280 8888 8990 8899 8467 8805 8545 8638 8195 8156 8085 8026 8184 7917 7579 7698 7555 7497 7446 7379 7183 7011 7111 6871 7218 7011 6812 6666 6582 6661 6419 6449 6289 6473 6262 6352 5965 6123 5860 5877 5953 5603 5525 5447 5439 5640 5306 5364 5261 5125 5447 5120 4983 4898 4841 4864 5064 4719 4635 4556 4554 4408 4440 4387 4506 4398 4501 4343 4188 4166 4252 4367 4116 4088 4155 3966 3899 3912 3976 3891 3997 3730 3679 3647 3660 3572 3619 3553 3441 3574 3562 3553 3397 3327 3380 3441 3250 3171 3226 3266 3173 3261 3317 3059 3002 3049 3060 3081 2977 2936 2943 2993 3269 2857 2920 2855 2695 2719 2831 2845 2853 2706 2683 2702 2740 3161 2565 2579 2552 2586 2409 2511 2441 2634 2460 2446 2397 2445 2426 2466 2198 2323 2387 2521 2279 2245 2161 2234 2169 2230 2177 2203 2186 2268 2156 2155 2108 2286 2089 2092 2081 1976 2123 1972 2098 1995 2007 1934 2092 1995 1959 1975 1902 1911 1870 1927 1798 1901 1763 1713 1874 1833 1806 1888 1947 1844 1826 1826 1913 1868 1762 1720 1717 1710 1862 1800 1804 1813 1792 1840 1785 1677 1617 1732 1836 1638 1568 1659 1717 1722 1720 1725 1663 1717 1624 1651 1624 1627 1589 1747 1757 1650 1597 1586 1512 1513 1597 1741 1686 1574 1631 1553 1686 1598 1561 1841 1603 1552 1559 1531 1551 1548 1561 1605 1468 1545 1486 1450 1615 1493 1455 1385 1388 1471 1460 1558 1400 1387 1459 1389 1403 1420 1420 1382 1358 1432 1332 1279 1460 1357 1334 1324 1245 1306 1236 1255 1233 1225 1200 1266 1200 1446 1464 1191 1201 1174 1129 1233 1125 1057 1185 1075 1188 1192 1173 1125 1153 1155 1805 1301 1232 1449 1271 1157 1247 1174 1150 1177 1224 1182 1155 1194 1239 1075 1150 1211 1271 1136 1106 1141 1125 1153 1076 1161 1137 1085 1038 1192 1097 1054 1042 1141 1022 1059 1068 1074 1047 1016 1099 1099 984 1001 992 996 1009 1048 1047 997 1008 1028 1015 1092 1042 993 995 1088 1103 957 998 1087 1053 1020 1310 1061 1003 1075 1017 989 1073 1195 1028 1035 1280 1081 1009 1058 979 1093 1075 1035 1129 1039 1148 1060 1013 998 1014 1107 991 1064 994 1087 1020 967 1023 960 971 988 984 1048 1003 1077 1090 985 1037 1006 980 972 945 965 1006 983 989 1006 879 852 870 861 855 903 839 832 861 1034 770 823 927 981 816 835 825 914 824 783 865 939 828 839 875 874 918 867 893 808 807 804 1169 916 812 809 770 843 893 772 837 730 788 794 836 717 762 759 736 730 739 690 731 739 778 769 819 816 821 852 830 753 671 699 736 773 775 705 748 727 707 696 720 722 928 720 697 720 713 723 726 691 734 757 715 823 677 726 769 716 698 752 1276 687 673 671 681 658 643 636 641 663 848 613 622 697 624 661 669 659 667 610 649 652 709 656 622 597 859 634 616 654 624 597 622 662 620 587 614 613 628 645 627 609 647 606 644 651 679 610 670 605 681 708 662 686 704 628 708 619 902 669 695 649 635 585 619 633 635 594 602 572 630 585 588 657 556 589 597 561 573 643 687 580 599 648 560 529 572 520 534 528 521 608 573 611 572 586 638 582 612 621 605 606 623 542 572 622 573 564 652 642 611 542 565 629 620 619 572 615 584 1214 593 598 624 559 531 517 581 533 548 534 593 571 539 521 561 513 521 848 621 525 540 481 469 491 460 462 487 512 515 546 442 454 561 558 565 471 480 471 520 459 416 430 429 404 392 371 380 404 394 356 386 397 388 391 372 355 426 379 388 379 354 365 339 378 320 390 381 578 356 404 331 323 374 372 362 338 317 332 364 344 340 365 380 411 394 379 363 386 363 355 394 402 391 411 426 559 639 376 421 499 469 491 436 524 298 454 458 454 428 449 444 378 396 435 390 372 379 423 414 408 411 392 413 416 433 410 451 405 370 350 398 358 373 440 404 394 347 373 377 339 364 351 370 337 345 347 323 335 338 330 314 316 251 292 243 244 227 246 260 232 291 239 223 252 229 208 230 201 216 221 228 219 226 230 212 250 225 239 247 257 243 252 334 247 229 235 245 227 258 234 209 244 216 201 251 247 218 228 251 263 218 210 239 208 179 224 170 193 170 172 181 213 180 204 200 187 176 194 174 187 181 200 218 206 210 189 170 177 191 206 196 224 213 155 181 186 190 209 179 173 202 206 201 229 164 147 170 202 252 151 181 168 164 176 191 155 179 185 183 178 161 299 180 193 206 177 251 209 200 172 202 175 179 173 178 136 151 196 179 166 188 172 179 163 146 179 170 192 184 167 164 161 176 177 175 185 168 187 196 203 182 161 176 203 176 193 189 195 193 178 184 187 235 201 173 198 165 168 161 174 160 188 240 192 173 165 209 169 185 215 187 191 165 179 155 161 177 149 189 166 145 199 160 165 151 257 151 139 131 152 166 167 141 150 165 152 138 137 129 131 159 161 110 141 139 147 136 134 128 166 148 143 122 140 129 160 174 208 170 168 168 174 185 155 155 166 176 164 166 174 161 181 102 136 138 132 111 115 140 119 126 106 142 117 144 159 133 134 133 119 133 136 221 125 116 125 91 107 103 103 107 181 96 100 82 70 81 78 160 87 90 87 91 117 116 101 108 118 105 109 113 117 106 101 164 113 127 150 93 123 168 107 122 133 114 111 102 105 106 132 122 83 96 86 98 87 91 70 99 102 100 88 103 115 115 98 97 82 108 105 97 87 98 94 100 104 92 72 102 98 86 92 87 102 124 83 99 105 86 77 73 85 81 81 77 92 83 96 80 89 94 62 91 85 67 75 83 77 79 56 63 58 50 80 70 53 59 62 54 62 64 73 55 56 44 51 59 54 64 94 53 68 62 54 50 62 60 80 63 66 54 68 48 61 63 59 61 62 71 72 62 69 75 84 74 57 82 61 76 60 81 70 52 92 69 76 60 58 69 61 36 63 55 64 69 58 67 56 73 58 65 63 59 49 64 75 68 60 64 79 66 59 73 57 60 65 48 54 66 59 57 41 49 43 43 50 37 59 53 52 54 49 61 51 50 55 55 57 65 55 68 45 70 60 49 61 60 66 44 130 56 59 68 51 87 63 44 54 62 61 54 48 43 49 50 44 46 50 47 58 70 58 33 45 48 48 28 39 44 45 39 38 45 41 45 47 39 34 60 59 50 57 53 48 44 59 63 52 77 67 59 61 60 52 61 73 80 70 78 77 86 81 86 95 84 70 73 87 74 91 109 111 84 99 78 82 90 84 94 97 108 98 95 100 114 112 85 108 87 74 69 76 91 83 66 82 89 68 62 58 64 52 71 67 74 54 64 74 77 63 54 46 43 69 61 50 67 85 75 73 50 49 51 42 39 42 39 35 49 35 45 47 52 39 29 44 30 36 45 41 53 47 47 48 36 36 31 60 60 51 53 54 37 43 49 57 65 58 42 43 38 38 50 42 42 53 51 53 58 59 64 72 60 64 57 74 59 57 56 69 49 45 59 48 36 33 55 58 55 47 45 54 51 36 46 52 42 37 42 43 60 45 24 35 30 35 27 25 28 35 34 23 29 32 32 34 35 34 33 23 25 33 32 30 32 30 34 27 22 32 25 29 24 23 28 15 22 28 24 28 23 36 40 25 27 29 35 26 20 30 21 25 28 22 20 18 20 22 24 46 26 29 20 24 29 24 34 39 20 41 29 32 26 30 31 31 36 22 30 33 42 41 30 43 27 35 26 36 29 42 37 31 35 33 24 29 18 34 28 18 25 25 20 21 24 17 21 22 12 22 24 13 18 10 14 13 12 17 27 13 19 25 19 39 23 24 20 26 16 26 38 24 25 22 21 21 19 15 11 16 22 19 19 13 19 29 24 42 15 20 22 18 27 18 30 24 24 23 26 29 39 25 29 29 32 23 34 37 27 30 
];
B = [
0 0 0
 102304 20960 81344
 121747 25891 95856
 127071 30057 97014
 108616 23849 84767
 124174 28214 95960
 152603 34871 117732
 165969 37908 128061
 193919 46172 147747
 253581 65466 188115
 168346 43389 124957
 443294 145857 297437
 119068 34648 84420
 92379 27833 64546
 64284 19633 44651
 46807 13418 33389
 35143 8689 26454
 38160 10064 28096
 25941 6455 19486
 37684 9347 28337
 36263 8602 27661
 62617 15715 46902
 62299 14825 47474
 73766 19398 54368
 60330 14463 45867
 85820 22646 63174
 77112 20687 56425
 155031 46573 108458
 51731 15540 36191
 142220 43092 99128
 57409 17958 39451
 57559 17135 40424
 50259 16605 33654
 58919 19959 38960
 44906 14507 30399
 50452 16990 33462
 47965 15261 32704
 39215 13223 25992
 60413 20333 40080
 50409 17473 32936
 44033 16172 27861
 63855 21261 42594
 41395 15711 25684
 102975 34818 68157
 55734 21548 34186
 37043 14800 22243
 51551 19271 32280
 56008 23527 32481
 59726 22483 37243
 65842 27592 38250
 44781 18026 26755
 47474 19204 28270
 72644 30564 42080
 45661 18576 27085
 91392 40982 50410
 66980 27194 39786
 93572 36911 56661
 51356 24951 26405
 72067 30028 42039
 142141 71091 71050
 28846611 17212036 11634575
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
5 38 2 0
0 10 0 0
3 16 1 0
10 16 2 1
7 19 4 1
10 25 4 1
14 27 18 5
91 32 79 13
600 49 375 69
10054 69 502 133
79874 102 560 246
289895 128 695 350
569019 222 944 557
841268 310 1172 908
973183 537 1647 1336
1011004 817 2268 2010
889263 1264 2965 2803
655066 1878 3981 3788
368217 2788 5276 5290
125655 3816 6706 6757
24843 5224 8621 8588
11721 7409 10500 10612
13191 10175 12609 12379
15738 12780 15143 15053
18794 15894 17834 17688
21404 19629 20833 20974
25410 24298 24396 24782
29393 29467 28856 28799
34088 33559 33019 33020
39096 38792 38568 38843
44029 43793 43539 43765
50107 49726 49040 49106
55895 55576 55245 55027
62119 62100 61476 61761
68059 68483 68245 67842
73909 74419 74124 74014
80489 81108 80366 80389
87262 86807 85979 86404
92423 93000 92588 92611
98937 99723 97798 98598
102656 103421 103018 103343
107089 107620 107644 106999
111243 112330 111732 111421
115443 115859 115553 115236
119673 119971 118858 119550
124809 124731 123249 123653
126114 126900 126036 125736
127872 128434 128499 128336
126505 127643 126312 127660
125621 125239 123750 125338
120843 121309 120874 120544
118008 118322 118234 118108
115241 114851 115824 115825
111736 110750 110599 111021
108008 107377 106669 107613
101986 102559 102506 102739
96077 96399 95592 96361
86853 86755 86793 87059
75710 76403 75659 75959
63735 64250 63860 64378
54046 55381 54638 55013
36548 36271 36329 36471
17068 17152 17235 17326
4409 4406 4462 4439
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
