A = [
575817 574740 2698733 182055 185259 172710 167662 173331 181913 190212 237874 272381 292395 354231 393832 397390 393616 392662 386167 379436 374539 366634 359451 358144 372574 506546 528413 566689 703252 644623 663895 660123 610917 630741 628046 631922 624862 613016 607551 600567 601633 596321 600018 609137 609011 614891 599897 591026 582861 565650 557750 554647 559017 558156 558341 558264 557529 553538 551548 545508 540441 540605 539185 537946 539571 535889 532151 533606 527155 522072 518844 511462 507307 506270 500350 497546 498521 492727 487818 485889 478186 471338 471113 465736 457108 458032 455307 448555 447719 443219 433274 430019 422002 417829 414010 412039 406372 406100 397266 392084 389016 382807 377319 372884 368569 362179 360910 355595 351595 348572 341523 337062 330689 325665 321417 316415 313706 308517 307166 303342 300732 297435 289699 284834 280336 275291 272697 269214 265650 261229 259580 254777 249559 246923 241768 236546 234082 230691 226515 225342 221784 217241 216345 210140 206227 203571 200054 196965 195246 191089 188147 186904 183943 179384 177003 174001 170626 168840 165712 163455 161947 158970 157216 154207 150426 147202 145477 141551 140611 138385 136443 134291 133536 130744 126802 126037 121580 119918 118940 115813 113795 112790 111242 108480 107169 104668 102631 100794 97860 96880 95549 93275 92007 91690 89135 86810 85430 83119 82380 80931 79866 78561 77136 75555 73413 72506 70947 69624 68692 66723 65414 64271 63471 62269 61901 60078 59149 57761 56741 55762 54563 54003 52975 52043 51163 50022 49085 47721 47016 46419 45310 44162 43869 43158 42722 41739 41232 40267 39558 38336 37796 37255 36409 36161 35321 34921 34229 33907 33192 31652 31623 30906 30609 29863 29656 29118 28449 27956 27456 28313 26619 26015 25360 25041 24794 23941 23536 23399 24377 22592 21670 21626 21568 21009 20482 20177 19575 19408 19248 18812 18571 18263 18000 17582 17061 17121 16543 16249 15732 15676 15187 14820 14811 14634 14082 14106 13782 13249 13232 13089 12909 12911 12346 12110 11851 11938 11566 11420 11254 11210 11179 10577 10646 10468 10509 10270 9827 9609 9719 9555 9199 9788 9441 8908 8770 8551 8509 8228 8247 8080 8208 8026 7740 7960 7723 7361 7223 7334 7343 7271 6916 6895 6580 6797 6566 6449 6520 6244 6076 6064 6319 5916 5914 5990 5639 5609 5441 5549 5384 5390 5250 5522 5442 5220 5293 5094 4996 4998 4940 5054 4857 4797 4832 4621 4646 4567 4769 4585 4420 4620 4443 4551 4314 4393 4233 4296 4244 4237 4516 4552 4145 4031 4073 4139 3875 4110 4038 4119 4226 4009 3781 4037 4023 3806 3995 3687 3717 3623 3587 3746 3736 3576 3668 3547 3693 3566 3406 3421 3363 3376 3594 3394 3340 3259 3164 3258 3140 3220 3361 3078 3257 3292 3178 3078 3077 3483 3160 3136 3182 3091 2950 2941 2928 2979 3110 3003 2872 2924 2937 2796 3015 2896 2762 2920 2899 2892 2874 2549 2880 2855 2795 2751 2740 2724 2747 2883 2879 2706 2657 2852 2690 2626 2574 2598 2670 2630 2852 2643 2586 2619 2467 2499 2556 2574 2537 2500 2462 2437 2566 2785 2302 2393 2419 2333 2380 2420 2496 2462 2423 2270 2303 2365 2389 2297 2351 2348 2296 2373 2277 2245 2191 2148 2165 2225 2259 2161 2163 2270 2040 2191 2067 2220 2100 2050 2006 2069 2120 1925 1931 1984 1964 1995 2125 1942 2031 1960 1908 1833 1837 1893 1798 1892 1742 1768 1850 1863 1938 1924 1899 1881 1765 1857 1873 1929 1804 1911 1696 1830 1831 1834 1810 1853 1899 1903 1826 1826 1762 1783 1899 1694 1682 1745 1744 1750 1706 1772 1687 1807 1661 1713 1768 1725 1711 1751 1910 1729 1717 1769 1692 1712 1768 1794 1683 1696 1645 1712 1642 1638 1649 1746 1679 1727 1566 1517 1643 1635 1531 1646 1637 1547 1576 1506 1729 1500 1493 1543 1541 1502 1579 1670 1490 1464 1454 1449 1445 1433 1526 1448 1418 1450 1451 1420 1445 1478 1319 1357 1282 1220 1245 1251 1144 1240 1292 1256 1222 1338 1514 1256 1248 1205 1262 1289 1299 1117 1157 1142 1180 1182 1234 1172 1215 1193 1505 1392 1243 1430 1181 1151 1271 1168 1207 1198 1095 1159 1253 1252 1237 1158 1093 1152 1233 1174 1146 1146 1208 1157 1092 1120 1180 1096 1051 1170 1059 1065 1105 1171 1158 1126 1108 1042 1029 1072 1102 1117 1133 1002 1100 1055 1117 1119 1080 1024 1077 977 1054 1173 1108 995 1030 1027 1011 1099 1050 1071 1122 1067 1389 1129 1028 1053 1077 996 1153 1320 1066 1101 1418 1140 1066 1128 1061 1117 1178 1088 1240 1022 1214 1105 1074 1063 1065 1121 1054 1099 1104 1020 1043 1040 1046 1053 986 1013 1054 999 1050 1047 1070 1104 1054 1028 1047 974 1019 1017 1000 1023 1062 1083 952 861 981 960 881 930 923 892 931 1107 881 871 910 1044 796 840 979 916 835 904 899 933 934 913 916 876 951 894 886 870 949 913 1305 949 867 829 851 850 912 879 824 869 785 871 1071 743 767 808 797 766 793 752 755 796 801 774 788 800 828 856 828 788 817 796 771 843 752 700 814 755 761 715 779 714 919 802 797 770 719 717 748 725 755 746 795 856 770 750 744 774 740 783 1115 744 711 755 726 727 691 701 674 612 823 676 646 630 698 678 663 655 620 673 733 717 803 596 683 631 937 644 632 664 648 622 607 696 696 650 704 635 661 654 619 664 654 650 647 636 716 695 726 692 752 744 697 758 748 739 756 738 974 742 804 743 683 674 678 670 722 694 646 629 633 603 682 734 667 673 652 662 641 675 672 603 628 661 611 611 678 609 574 601 573 578 617 690 561 669 618 599 619 685 661 639 653 659 619 738 648 584 740 773 685 599 634 705 644 729 730 662 677 1490 720 646 668 614 581 573 575 626 554 580 661 588 632 612 623 567 544 1002 713 588 560 539 552 514 496 484 515 523 606 578 506 492 614 549 569 514 510 516 441 511 486 457 428 437 435 374 382 421 373 379 391 424 400 369 415 396 409 393 386 388 400 337 373 404 378 347 353 607 396 387 385 387 387 368 376 371 355 397 374 398 401 352 365 423 382 450 403 421 408 401 422 396 387 437 434 590 764 428 471 535 525 573 485 586 411 560 560 537 478 498 547 479 509 453 470 433 445 494 471 388 483 460 506 465 469 445 484 462 457 456 452 420 446 477 409 485 408 425 463 347 437 399 434 384 365 335 363 388 382 337 361 329 289 265 303 229 253 266 234 236 244 247 247 266 265 251 285 253 260 263 257 233 272 207 231 239 247 272 262 265 258 261 324 281 252 270 270 265 253 223 219 228 246 244 252 269 279 279 246 277 238 221 227 250 240 221 203 181 171 182 187 176 209 204 202 198 204 188 195 208 203 183 193 193 184 203 232 182 183 217 203 246 219 191 207 220 189 167 202 193 178 214 228 259 168 176 173 172 216 195 161 156 146 197 187 150 156 192 164 178 150 253 170 225 209 164 301 189 208 183 193 189 180 185 178 152 169 182 199 186 163 184 177 201 152 172 166 206 213 184 176 177 158 162 186 186 205 236 203 217 210 186 213 204 210 191 220 199 217 198 188 226 290 218 173 177 203 200 182 179 215 218 254 196 207 220 237 193 198 261 194 196 205 185 185 190 171 170 187 169 158 237 183 200 152 244 186 135 157 159 194 140 169 165 179 168 166 160 148 153 152 144 131 154 120 136 129 173 132 162 156 161 145 132 149 163 215 194 196 236 212 207 177 178 149 180 186 185 201 175 172 200 124 124 102 157 137 127 136 125 145 127 166 152 148 140 120 137 182 123 140 132 256 116 151 113 107 129 86 79 106 153 93 91 86 105 92 99 140 119 85 79 95 112 112 97 106 108 147 105 107 120 93 103 102 112 109 96 121 142 162 110 110 136 108 134 95 115 88 114 102 81 109 94 82 84 60 65 89 102 106 114 92 106 108 85 110 100 89 113 96 87 91 99 99 95 94 86 84 81 119 85 80 119 89 80 88 103 103 80 84 81 83 82 69 88 88 93 92 95 67 61 80 91 81 77 67 93 86 79 79 94 46 67 58 54 62 41 44 67 56 73 77 77 70 56 69 51 58 101 46 52 50 48 57 60 59 57 56 57 67 51 41 60 63 57 65 69 80 78 56 68 71 73 53 66 76 67 87 64 87 76 67 73 61 67 88 61 72 73 41 50 61 64 70 54 56 75 47 59 63 62 66 55 72 64 71 84 74 69 56 58 61 67 64 55 50 48 47 57 55 41 33 51 53 26 36 45 54 38 52 40 46 57 54 62 57 52 44 55 61 47 46 57 44 72 71 62 59 102 71 62 51 70 72 44 45 49 46 41 43 44 46 46 46 52 46 56 45 57 48 68 50 38 32 45 32 43 34 32 34 41 55 49 38 40 43 43 45 52 60 51 59 72 61 57 63 58 70 52 64 62 52 61 87 63 87 95 67 75 100 85 88 86 97 86 107 109 87 98 110 101 87 70 98 101 102 87 77 116 124 97 101 121 128 120 101 79 94 80 97 90 83 74 66 79 92 82 82 73 78 58 67 63 77 79 70 66 63 60 77 63 65 60 44 72 75 81 77 72 55 62 44 40 45 45 40 44 44 35 36 40 47 34 41 48 45 46 42 36 47 46 47 38 36 33 45 64 52 43 46 45 36 40 46 41 35 32 54 49 54 31 42 55 48 51 54 49 53 40 50 53 49 56 57 60 53 64 68 58 47 46 73 42 55 38 52 51 38 46 55 55 33 37 49 38 63 49 41 48 45 36 37 42 41 38 46 25 16 15 29 34 20 30 44 28 36 33 25 34 35 26 33 28 28 33 30 27 16 24 26 20 19 19 13 29 18 20 26 30 26 25 25 16 36 25 30 24 22 28 23 22 20 20 22 20 21 25 34 36 24 19 29 27 33 22 37 34 34 23 39 31 35 33 23 33 24 28 34 27 52 27 36 42 36 56 34 32 32 22 34 36 35 34 26 34 16 36 19 26 16 33 16 20 15 18 13 20 16 24 21 10 11 10 14 15 16 13 17 14 20 21 18 32 19 15 9 20 25 26 27 12 15 20 18 14 15 5 11 16 11 14 14 15 19 16 17 12 27 21 29 19 29 28 15 22 18 16 24 16 20 19 19 15 27 23 12 24 12 17 
];
B = [
0 0 0
 114732 23309 91423
 134118 28035 106083
 143702 33510 110192
 120249 25577 94672
 135126 30399 104727
 167397 37789 129608
 182374 40654 141720
 215678 49799 165879
 282086 71649 210437
 189063 47556 141507
 501071 160883 340188
 140993 40070 100923
 110261 32346 77915
 74572 22409 52163
 55234 15338 39896
 40084 9535 30549
 42984 11246 31738
 30059 7143 22916
 42621 10173 32448
 39881 9085 30796
 70418 17424 52994
 70720 16459 54261
 81720 21478 60242
 70422 16724 53698
 97914 25161 72753
 84587 22092 62495
 181907 54000 127907
 57109 16729 40380
 157405 47266 110139
 64927 19822 45105
 64544 18434 46110
 55620 18060 37560
 66650 21760 44890
 49592 15587 34005
 56673 18357 38316
 52512 16216 36296
 43217 14061 29156
 65972 21642 44330
 55796 18880 36916
 48665 17335 31330
 69439 22270 47169
 45066 16371 28695
 112556 37394 75162
 61748 23394 38354
 40917 15692 25225
 57118 20872 36246
 62463 25226 37237
 68114 24936 43178
 73566 30135 43431
 48979 19324 29655
 52161 20541 31620
 80676 32545 48131
 50016 19617 30399
 105239 45930 59309
 74265 29316 44949
 102089 38985 63104
 56720 26959 29761
 80259 32851 47408
 170077 84203 85874
 33782501 19800413 13982088
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
12 40 0 2
0 10 1 0
5 11 2 0
8 12 0 1
7 12 8 1
11 24 13 4
17 21 15 7
121 33 77 14
744 59 377 71
8995 76 463 152
75165 95 627 272
332062 148 812 490
721221 212 1148 738
1070379 371 1492 1214
1243155 667 2097 1761
1280135 1138 3001 2769
998398 1665 3990 3904
523183 2563 5304 5251
155355 3663 6945 7043
29589 5214 8909 8815
13099 7117 10895 11071
13985 9754 13279 13413
16640 13072 16084 16282
19431 16579 18853 19017
22880 20505 22301 22262
26054 25038 25953 26232
30778 30043 30088 30011
35817 35931 35085 35372
40660 41083 40160 40283
46801 47439 46414 46426
52467 53713 52694 52594
59311 59459 58460 58451
65917 66298 65437 65095
72561 73459 72833 72752
80743 81128 79743 79490
86827 87717 86789 86749
94450 95298 94060 94971
101354 101669 100427 101192
107519 108867 106945 107826
114672 116061 112950 114213
119091 119087 118876 120006
123808 125107 123842 124576
128248 128839 127896 127613
131279 132477 131967 132143
136146 136611 135781 136090
141551 141665 140290 140446
144264 144329 143822 143148
146628 147122 146205 146399
146909 146871 146330 146988
144824 145162 144954 144448
139795 140435 139744 140727
136458 137792 137030 137222
132370 132910 133283 133384
129299 128403 128189 129111
124491 124057 123563 125050
118075 118355 118408 118784
111819 111852 111288 111731
100795 101299 100258 101382
88306 89070 87792 89359
74654 75636 75167 75364
63263 64502 63627 63976
42311 42876 42876 42773
20321 20580 20631 20406
5169 5036 5268 5072
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
