A = [
119854 117464 328354 87495 83864 83350 79656 81256 84368 83460 90778 121619 162853 190988 246084 302730 329292 353805 361502 352892 350023 332697 314554 325697 331715 380847 395449 394809 434053 384098 383010 372027 315804 319496 319689 317858 307235 306840 306742 294192 301628 301081 298349 311993 308735 304780 306260 301600 292158 290446 286236 281839 293536 293145 285054 293934 297211 289922 296933 291337 283701 293312 291610 286496 295863 295728 286515 296969 293332 285178 292584 288188 282176 292640 288136 282454 290430 285517 277404 284272 284406 273870 279907 277016 269145 275270 274836 266127 274681 269025 258483 264753 260626 255287 261589 257294 248690 254160 251696 243274 248138 244536 234337 240561 238718 231353 234196 232232 225616 230698 225070 217893 220018 215858 210123 215085 210092 207427 208863 203882 197357 203788 199059 191972 194059 191442 184655 189060 185376 179481 182052 179686 175768 177381 175380 166454 169125 166755 161235 164501 162347 156106 158322 156164 151046 152255 151750 146022 149529 145398 141889 143371 143655 137773 136796 136066 130810 133360 131769 127064 128760 126123 124552 123920 122719 119309 119766 117761 112862 115446 114609 111033 112118 111410 105534 107623 105415 103350 105053 102404 98666 99539 98210 94744 97007 93653 91577 91032 90294 87384 89920 87768 84547 86337 82870 81012 82134 81000 78365 78766 78443 75252 76411 75153 73290 73420 73001 69728 70765 69098 66756 68493 65878 64675 66079 64782 62356 62429 61873 59490 60737 59761 58767 57643 56754 55717 55588 54516 52678 53728 52219 50223 51129 50555 49245 49765 49352 48042 47552 46759 45038 46344 44510 43441 44588 43815 42229 42579 41531 40779 40513 40007 39235 38431 38573 37177 37879 37373 35826 35958 35904 34759 34260 33929 33260 33263 32930 32589 31967 31366 30130 30260 30581 28824 29473 28850 27703 28320 28104 26788 26464 26691 25350 26156 24989 24663 24472 24472 23386 23721 23401 22678 22676 22280 21467 21575 20816 20874 21255 20487 20414 19968 20190 19070 19601 18963 18646 18822 18197 17705 17922 17682 17624 17150 17099 16723 16487 15518 15980 15591 15148 14887 15242 15251 14203 14420 14105 14053 14046 14164 13324 13567 13350 12882 12767 12757 12356 12094 12551 11660 11786 11847 11203 11347 11262 10894 10212 10769 10215 10606 10505 9985 9769 9710 9374 9787 9321 9258 9631 9062 8909 9172 8717 8461 8413 8262 8282 8214 8033 7830 7615 7633 7601 7495 7302 7420 7748 7059 7225 7068 7023 6769 7009 6849 6545 6886 6815 6441 6291 6470 6199 6348 6058 5948 5951 5980 5783 5765 5629 5642 5455 5531 5612 5448 5181 4941 5155 4921 4771 5046 4753 4869 4888 4842 4936 4768 4614 4530 4468 4360 4248 4312 4119 4196 4147 4133 4195 3831 4162 4229 3964 3907 3923 3855 4069 3847 3608 3797 3697 3742 3553 3593 3522 3304 3629 3242 3276 3245 3296 3296 3273 3039 3190 3096 3331 3065 3295 3106 3007 2972 3005 3001 2912 2844 3095 2831 2891 2621 2657 2829 2863 2615 2418 2482 2481 2709 2425 2421 2588 2611 2480 2451 2439 2494 2731 2518 2355 2314 2500 2441 2421 2216 2107 2458 2112 2260 2278 2234 2148 2115 2183 2102 2317 2032 1955 1996 2078 2202 2306 1881 1886 2029 1995 1943 1922 1983 1869 1889 1803 1880 1832 1939 1840 2029 1870 1924 1842 1726 1794 1806 1746 1878 1748 1764 1724 1583 1809 1765 1735 1781 1625 1817 1699 1663 1690 1775 1775 1641 1667 1670 1467 1537 1566 1478 1765 1487 1671 1576 1658 1583 1681 1507 1479 1608 1565 1691 1719 1474 1643 1401 1445 1372 1494 1416 1531 1531 1400 1402 1440 1496 1518 1566 1450 1533 1339 1495 1356 1407 1391 1530 1563 1579 1336 1428 1335 1634 1489 1672 1445 1412 1363 1341 1360 1429 1440 1431 1345 1456 1388 1383 1490 1305 1388 1291 1248 1104 1301 1295 1280 1272 1321 1251 1372 1244 1275 1347 1219 1312 1374 1256 1180 1097 1221 1244 1213 1074 1130 1046 1181 1067 1159 921 1131 1145 1058 1086 1144 1086 1161 1085 1096 1186 1114 1076 1114 1098 1234 1129 1141 1089 1098 1021 1089 1272 1185 1015 1218 1079 1119 1341 1089 1029 974 1017 1038 1155 1075 1055 1091 1018 984 1012 1081 1026 1129 957 1019 1067 1040 953 970 973 954 1012 1036 933 926 869 896 866 831 961 841 831 938 861 914 883 796 897 829 967 842 879 847 861 933 881 969 861 903 938 807 818 931 856 999 959 872 1033 911 889 973 780 993 808 1005 1008 922 975 967 940 977 1074 919 1047 1062 988 945 831 890 934 966 942 958 956 898 896 878 882 824 899 944 943 816 955 932 1037 833 921 804 831 836 765 883 897 858 727 784 784 812 911 794 807 865 814 830 696 707 759 873 681 587 674 681 645 724 653 835 821 802 799 802 744 693 726 785 706 734 796 693 736 746 699 657 754 697 675 599 702 679 696 628 683 739 702 625 638 667 749 689 723 725 664 671 727 586 798 603 634 662 685 625 764 663 711 673 819 615 707 645 764 720 573 700 722 702 825 673 704 637 624 623 654 542 618 593 618 560 638 737 510 525 522 548 647 550 508 646 578 476 535 598 553 581 769 502 550 637 658 620 636 622 612 614 478 571 672 563 541 575 629 664 690 521 647 572 609 664 602 528 547 517 628 635 554 602 643 497 505 649 590 547 644 614 607 534 639 536 569 580 511 512 599 581 469 441 512 447 567 538 661 422 543 577 615 605 554 589 482 601 548 488 600 554 416 511 567 391 497 485 484 629 503 433 528 627 542 622 482 512 431 506 500 516 469 458 533 670 449 590 641 664 691 835 453 588 624 564 399 477 443 457 539 383 404 496 493 494 442 478 445 590 402 505 383 423 468 506 405 435 461 464 452 512 518 452 552 415 458 455 347 357 373 466 381 554 434 463 422 423 371 344 354 383 365 296 406 340 315 494 376 328 301 346 321 367 283 335 338 238 302 359 358 321 293 272 314 331 408 361 288 268 337 385 307 263 252 289 327 259 333 315 264 300 349 366 256 368 344 346 335 324 363 298 315 308 338 337 379 392 294 346 396 286 434 420 645 379 410 431 303 335 258 468 255 278 308 334 321 344 258 476 435 373 436 317 294 342 283 298 409 373 311 301 296 288 374 345 227 302 310 387 340 267 278 323 340 255 342 270 297 176 240 254 212 174 180 200 199 192 254 161 208 176 239 187 190 234 244 239 225 148 227 185 199 210 229 178 235 227 215 160 183 177 168 184 187 206 212 198 216 211 146 218 226 252 266 232 169 139 176 188 193 190 219 125 190 132 137 118 188 177 182 172 198 153 152 166 199 201 155 134 188 168 141 182 125 211 201 214 179 196 135 223 145 188 145 161 120 155 122 209 159 230 125 136 187 176 176 158 172 169 146 167 124 121 138 125 140 152 119 148 141 175 192 149 141 139 170 124 153 132 124 138 129 124 145 151 92 137 160 115 128 125 108 165 194 131 176 197 150 98 101 119 121 187 157 123 173 187 120 152 165 130 119 152 119 140 183 142 148 123 145 163 132 142 109 162 120 110 145 129 139 151 162 202 137 188 160 209 139 110 141 161 140 111 127 147 207 161 217 137 167 112 167 132 113 148 131 112 145 139 199 175 106 137 141 128 176 150 142 108 152 148 101 90 62 174 127 159 136 111 114 138 125 172 121 280 108 176 155 206 168 157 182 143 118 131 146 130 132 105 102 111 107 127 167 148 125 104 135 115 75 118 143 122 88 140 144 111 109 137 102 133 105 86 66 131 62 121 98 92 79 91 95 101 77 82 83 71 67 116 124 112 96 107 118 89 161 178 120 142 121 139 137 105 104 110 121 142 115 120 110 162 132 70 109 68 108 128 80 59 112 70 97 80 62 67 90 98 131 100 138 165 97 79 115 62 55 103 85 74 98 118 100 100 80 128 86 175 97 85 91 87 70 63 106 97 74 65 139 49 99 92 74 67 69 80 79 109 50 75 47 78 60 53 77 67 58 72 77 52 47 74 44 52 26 41 57 39 37 52 66 62 39 78 31 33 26 37 57 49 71 72 44 63 77 42 33 71 63 50 60 92 112 43 83 39 77 74 59 95 29 67 87 84 66 75 87 66 48 60 74 39 59 69 54 59 46 42 35 41 80 48 71 80 78 62 63 51 54 57 66 65 71 61 74 59 96 80 72 27 71 36 64 41 58 53 71 52 40 38 65 47 46 48 58 37 36 58 40 62 33 38 47 63 55 79 63 53 44 53 57 34 49 69 45 75 67 41 36 83 47 55 63 30 49 68 54 59 45 61 44 55 37 30 65 47 30 58 34 49 38 29 44 40 25 48 52 23 41 76 51 48 69 39 32 55 63 82 46 47 53 59 72 68 59 66 54 64 46 50 61 56 55 63 42 97 125 122 63 36 121 109 69 102 91 93 107 104 96 87 54 40 79 89 53 84 67 148 108 75 82 131 93 98 119 65 78 94 37 95 51 58 71 55 65 58 90 79 64 49 53 62 43 56 52 55 51 78 45 38 57 48 61 61 65 75 56 51 52 48 43 44 45 53 38 30 24 41 56 29 43 42 65 34 27 46 51 46 54 33 27 15 53 54 79 54 35 38 69 59 47 47 44 56 54 47 53 61 46 33 38 50 24 33 42 69 49 45 72 46 59 60 72 100 49 83 53 65 60 73 48 45 66 51 37 74 63 39 59 48 71 39 39 36 54 35 49 23 73 15 38 27 36 43 9 19 30 45 39 35 29 36 14 26 14 34 19 20 24 66 17 22 23 20 66 37 51 25 30 8 28 37 32 13 29 32 12 13 26 21 27 42 25 30 35 27 29 23 23 21 17 16 22 19 23 24 22 31 35 45 41 43 27 41 34 19 43 28 9 19 32 24 32 12 16 34 15 41 40 35 40 38 37 28 42 27 35 40 29 78 14 53 19 55 25 22 31 21 12 30 10 18 5 16 28 23 21 12 17 36 22 8 12 17 16 13 19 16 15 17 30 19 11 21 20 19 21 26 9 11 33 38 19 20 14 22 37 5 34 19 23 13 21 28 21 18 24 23 37 32 17 27 32 40 43 23 43 33 41 34 22 10 30 60 26 30 10 
];
B = [
0 0 0
 69680 17180 52500
 84270 21307 62963
 90744 26274 64470
 77775 20809 56966
 90131 24602 65529
 106287 30642 75645
 118135 33738 84397
 137183 40552 96631
 186602 59911 126691
 104003 32052 71951
 317781 129302 188479
 76699 27203 49496
 63767 24635 39132
 46839 18801 28038
 33318 11891 21427
 23219 6964 16255
 27490 8973 18517
 18232 5224 13008
 25031 7466 17565
 24617 7019 17598
 42156 12609 29547
 41220 12033 29187
 49765 16095 33670
 40052 11837 28215
 54473 17479 36994
 50545 16828 33717
 102919 37815 65104
 31153 11360 19793
 102801 38718 64083
 37910 14303 23607
 37664 13070 24594
 33365 13590 19775
 40273 16603 23670
 30129 11406 18723
 35196 14458 20738
 31011 11616 19395
 25792 10305 15487
 39140 15727 23413
 32920 13719 19201
 30392 13388 17004
 40433 15428 25005
 27076 12144 14932
 73123 28612 44511
 34965 15823 19142
 24142 11461 12681
 35550 15966 19584
 36087 17739 18348
 39445 17616 21829
 43473 21267 22206
 28201 13286 14915
 31527 15026 16501
 46017 22326 23691
 31117 14690 16427
 52848 27354 25494
 43264 20589 22675
 58361 25410 32951
 33197 18624 14573
 49123 23568 25555
 81081 45216 35865
 21264738 14637283 6627455
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
0 3 0 0
3 1 0 0
0 5 3 0
4 0 0 3
6 9 2 3
12 3 7 8
24 1 35 23
67 7 29 41
1373 9 64 54
12267 9 96 81
65720 18 174 158
301622 32 263 256
771946 59 377 355
1114785 119 654 600
1102304 232 856 905
963145 339 1442 1482
727100 746 2057 2027
453105 1199 3060 3131
224563 1823 4157 4109
76591 2781 5489 5382
18158 4000 6635 6870
10235 5957 8136 8381
10684 7697 9961 10117
12884 10255 12098 11954
15169 12670 14725 14366
17309 15800 17273 17231
20753 19721 19842 20156
23360 24295 22862 23522
27118 26825 26398 27387
31588 30620 30893 30784
35295 35425 34537 34909
38930 38593 38037 38278
43100 41997 41839 41784
46405 45096 44755 44936
49268 49722 48186 48685
51602 51463 51747 51982
53933 53768 54096 54020
57210 57079 56711 56539
59965 60784 59689 60012
64631 63990 62607 62673
65636 66090 65379 65598
69481 69154 69833 69924
72827 72633 72710 71953
77340 76773 76582 77090
81342 81099 81191 80647
87201 87435 84917 85862
90814 90709 89098 89968
95311 95255 94441 92517
98055 96720 98183 97681
100795 100204 99164 100243
101238 102209 103520 101771
104083 104202 103751 105035
104310 103666 105905 106045
101701 102634 101455 103116
100099 100810 100522 101005
96583 97241 96898 97056
90024 91708 91070 91412
81751 82399 80521 81726
70388 71802 70501 71083
57525 58479 57233 58837
47455 49306 47506 48159
30396 31986 30534 30936
12576 13808 12975 13251
2660 2672 2735 2426
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
