A = [
142142 32739 32630 414092 19506 23986 23664 23558 25784 25807 29582 28529 29103 30392 31135 30829 30399 30747 30794 30575 30523 30286 30411 31522 162846 160800 162247 163095 167829 314065 311299 311060 312046 311430 325028 323611 321647 322229 319738 319640 318492 317735 316006 314251 314084 314299 311416 310527 309417 308137 305361 304179 304568 304437 303455 301101 301994 298807 298756 298086 295578 295221 293367 290747 290571 289101 287573 285700 286345 280908 281547 278368 276374 275324 274256 271898 270237 268942 264802 262596 260895 257533 258248 256880 253982 251391 248875 247355 243987 242323 238834 237685 235242 231642 230288 228413 225711 222965 221795 219806 216591 214629 210225 209714 206803 204668 203605 199514 198243 195745 192828 190806 188111 186358 183240 180833 179853 177193 175011 173558 170623 169114 166488 165411 161855 160797 158083 156242 154443 151857 149470 148065 147120 143269 141819 140553 138963 137955 135835 134138 131457 129107 127201 125830 124118 121770 120736 119519 117184 115980 115253 113566 111437 110474 109006 106912 105565 103880 102763 100670 99303 98428 96401 95835 94950 93304 91341 90036 89168 87447 86038 85864 84191 83342 81333 80464 79216 77990 77009 75939 73909 73705 72403 71241 70255 69479 68715 68072 66177 65144 64580 63199 62729 61543 60974 59779 58889 58537 57666 55908 55826 54938 53866 53716 52339 52185 51113 50134 49643 48740 48685 47773 47301 46538 45534 44867 44276 43846 42880 42373 41651 40868 40605 39544 39433 38772 37971 37354 37000 36475 35849 35475 34695 34491 34229 33321 32750 32274 31829 31470 30845 30647 29950 29545 29112 28898 28183 27723 27764 27225 26697 26773 25965 25674 25294 24637 24682 24337 24043 23685 23351 22878 22360 22351 21908 21583 21201 21186 20979 20617 19927 19585 19687 19160 19015 18653 18268 18125 17985 17729 17613 17390 17230 16688 16576 16017 16118 16154 15508 15414 14973 14847 14521 14266 14278 14437 13963 13761 13658 13552 13118 12950 12954 12651 12453 12210 12021 11842 11698 11623 11440 11372 11176 10861 10792 10813 10584 10379 10228 10058 9797 9718 9904 9594 9354 9318 9484 9011 8958 8785 8854 8679 8484 8370 8453 8129 7957 7982 7953 7902 7823 7388 7448 7379 7383 7107 7234 7127 7047 6762 6882 6622 6517 6423 6340 6272 6151 6192 6129 6098 6259 5942 5876 5688 5693 5628 5633 5539 5428 5346 5310 5380 5162 5093 5049 4974 5007 4850 4851 4829 4893 4624 4605 4556 4535 4575 4308 4337 4269 4337 4326 4151 4145 4072 3998 4039 3946 3893 3856 3890 3846 3822 3753 3710 3690 3688 3556 3567 3514 3602 3375 3306 3472 3465 3342 3336 3152 3193 3138 3072 3213 3165 3095 2993 3025 2814 2862 2961 2905 2804 2927 2754 2771 2775 2676 2832 2761 2578 2757 2671 2611 2522 2673 2558 2606 2529 2606 2427 2375 2545 2478 2434 2353 2395 2371 2330 2327 2301 2366 2287 2241 2287 2296 2311 2287 2320 2226 2225 2132 2117 2132 2058 2111 2095 2094 2089 2120 2116 2102 2044 2059 2076 1956 1998 2034 1955 2038 1947 2004 1999 1904 1971 1899 1955 1916 1924 1921 1852 1864 1838 1878 1796 1804 1835 1768 1866 1759 1840 1758 1824 1735 1764 1814 1770 1732 1720 1750 1657 1796 1773 1767 1742 1732 1676 1687 1647 1702 1596 1709 1599 1647 1609 1543 1629 1627 1665 1514 1624 1543 1554 1549 1534 1554 1549 1467 1535 1513 1498 1446 1440 1469 1478 1507 1534 1400 1428 1490 1454 1539 1433 1412 1435 1527 1435 1440 1451 1449 1390 1458 1478 1456 1383 1483 1391 1380 1421 1370 1400 1346 1402 1418 1336 1435 1392 1412 1333 1313 1364 1460 1415 1424 1421 1396 1399 1409 1385 1385 1401 1361 1397 1325 1395 1370 1392 1422 1439 1385 1366 1329 1348 1312 1431 1396 1340 1319 1332 1375 1356 1360 1308 1288 1280 1347 1250 1223 1314 1344 1347 1326 1238 1266 1304 1399 1328 1310 1289 1298 1248 1285 1236 1315 1291 1286 1285 1275 1286 1311 1296 1239 1275 1310 1189 1298 1246 1295 1221 1330 1254 1322 1269 1267 1177 1262 1225 1289 1279 1300 1276 1256 1227 1204 1251 1247 1197 1203 1199 1162 1176 1225 1213 1241 1222 1283 1211 1215 1213 1185 1225 1223 1250 1207 1196 1216 1264 1211 1198 1204 1297 1244 1229 1233 1248 1221 1277 1209 1271 1227 1286 1298 1264 1251 1311 1228 1225 1298 1310 1210 1209 1243 1286 1250 1156 1293 1205 1229 1207 1350 1274 1189 1265 1232 1269 1254 1198 1223 1297 1245 1220 1178 1234 1219 1292 1275 1258 1193 1129 1290 1225 1228 1179 1263 1227 1214 1211 1207 1226 1126 1209 1158 1221 1232 1189 1143 1179 1166 1138 1222 1115 1185 1178 1218 1161 1116 1261 1153 1128 1255 1181 1140 1195 1187 1190 1122 1189 1217 1220 1207 1199 1133 1183 1103 1157 1198 1142 1153 1165 1197 1141 1206 1157 1126 1058 1118 1165 1083 1126 1081 1069 1042 1078 1108 1100 1035 1072 1046 1045 1156 1059 1147 1129 1152 1097 1109 1101 1077 1059 1114 1066 1133 1132 1065 1210 1150 1105 1100 1098 1131 1082 1040 1129 1064 1139 1137 1038 1072 1121 1099 1088 1122 1080 1110 1174 1075 1142 1135 1039 1085 1111 1076 1043 1092 1029 1101 1160 1131 1115 1117 1122 1082 1119 1060 1117 1100 1110 1075 1136 1094 1084 1125 1123 1096 1100 1175 1107 1092 1156 1109 1129 1084 1138 1156 1086 1130 1125 1141 1109 1077 1124 1163 1087 1052 1132 1053 1114 1092 1155 1084 1077 1138 1024 1145 1147 1109 1107 1072 998 1108 1074 1164 1159 1182 1095 1171 1115 1096 1137 1161 1165 1131 1036 1111 1054 1126 1044 1131 1081 1052 1068 1067 1078 1093 1101 1072 1148 1058 1130 1085 1102 1133 1112 1053 1106 1088 1113 1139 1105 1035 1073 1101 1143 1143 1078 1016 1092 1024 1066 1008 1082 1078 1132 1090 1152 1117 1099 1013 1083 1105 1103 1043 1033 1023 1047 1079 1024 990 1017 1084 1084 1014 1124 1081 1078 1007 999 1048 1047 1144 1027 1109 1104 969 1061 1022 1064 1042 1012 960 1034 1006 1060 1045 1009 1021 1018 1078 1096 1064 999 1017 1116 1035 1070 994 982 1062 1080 1036 998 1024 1038 1006 1032 1018 1040 1072 970 958 979 951 993 1035 999 969 1083 984 977 970 982 974 1003 1017 966 951 996 942 938 923 914 984 921 1011 972 914 926 940 977 960 937 930 1023 922 967 1000 1025 988 1014 976 972 1007 997 1012 989 992 1024 945 1048 1021 972 970 909 981 983 1032 1026 959 930 964 932 961 1001 1008 963 962 1038 970 1020 957 948 986 982 1036 1011 1019 945 1017 999 983 1060 909 973 1018 1091 969 1031 1020 994 1039 1023 1027 1054 1011 1103 1026 1016 986 1052 1028 977 1006 984 986 937 1000 1056 1078 1090 982 1036 1054 1031 1073 1036 1000 1032 1041 1037 981 1053 1040 1029 1034 1021 1025 984 972 1019 991 1052 995 1048 983 926 977 1022 924 1000 1009 1001 979 1013 1000 1020 1006 1028 952 971 1004 958 1001 978 1013 981 1007 954 994 913 921 1021 1083 947 957 901 955 952 946 987 938 904 950 931 935 934 927 954 954 893 905 951 933 937 842 909 898 832 895 867 844 922 934 895 854 815 887 895 841 897 805 851 860 826 890 839 823 828 836 848 864 874 896 880 867 899 849 938 893 860 917 924 865 857 888 855 891 898 893 865 890 862 863 879 891 935 823 900 866 931 878 907 948 908 944 916 941 957 904 933 898 1005 867 971 1013 900 958 1032 878 960 931 962 976 903 936 993 934 941 907 915 903 915 996 907 950 946 947 915 949 901 898 967 929 1003 946 982 968 939 892 876 934 898 924 905 903 858 906 950 912 910 845 913 922 882 956 872 845 863 877 905 915 861 869 914 951 853 854 813 873 844 899 879 815 889 921 923 863 935 925 878 888 867 950 877 897 882 855 860 873 846 837 934 915 828 858 862 844 830 851 864 854 829 871 822 862 831 811 806 807 869 838 875 841 777 803 917 824 775 834 877 862 847 911 795 831 816 802 754 820 836 796 769 791 804 812 794 831 819 818 766 829 805 835 797 753 831 830 849 818 750 752 812 804 790 803 814 784 829 804 788 770 746 845 813 805 803 788 796 832 763 790 797 797 842 726 781 838 776 793 833 800 817 842 827 767 787 772 818 849 816 708 752 800 807 814 823 773 767 760 804 784 724 787 739 760 783 727 775 792 773 777 750 724 771 736 726 746 790 742 730 762 768 737 769 764 738 757 733 744 773 807 754 839 768 803 804 778 778 783 709 785 709 816 748 781 741 818 740 794 804 728 724 750 753 730 751 736 751 708 813 766 777 801 791 816 776 776 823 773 718 726 777 748 759 762 757 743 768 738 725 699 706 759 724 736 738 746 685 708 721 732 751 684 715 741 737 646 703 712 686 700 691 672 692 692 753 703 768 766 708 724 747 699 742 718 772 724 769 713 763 775 708 731 676 797 730 750 757 734 766 719 757 775 781 758 772 779 707 741 827 776 788 713 801 823 771 769 810 788 795 774 749 792 806 733 791 739 736 781 823 799 765 750 795 801 799 826 722 756 793 791 747 796 763 804 781 689 731 733 755 753 780 774 779 703 744 747 741 730 773 751 726 719 743 683 708 714 710 730 722 716 728 705 705 700 684 693 763 731 738 764 658 727 739 658 720 653 708 672 651 730 747 672 673 663 654 723 725 691 762 679 704 683 757 713 726 741 718 743 716 674 747 699 670 744 727 747 659 657 712 693 706 749 697 682 722 749 676 711 742 701 757 719 673 715 697 740 688 648 692 755 741 696 697 732 800 738 740 737 725 699 694 731 669 700 707 748 720 712 704 733 726 715 721 732 679 746 714 730 739 719 716 724 734 770 670 690 705 729 718 702 712 697 709 679 674 699 676 720 733 702 703 691 671 700 669 689 655 659 750 704 742 704 695 665 754 709 669 741 779 761 720 718 711 706 684 695 695 740 671 639 691 677 657 687 700 676 696 677 628 697 660 629 681 695 726 720 704 717 719 739 761 694 656 645 738 733 658 691 688 657 712 656 724 659 626 626 688 661 700 683 732 686 667 689 632 686 674 687 692 697 683 672 685 675 685 675 656 613 651 631 697 720 678 637 669 687 647 597 607 667 649 636 709 664 635 625 632 678 641 638 616 675 681 665 633 666 622 704 633 642 634 606 601 597 610 612 604 614 596 589 668 604 609 593 594 625 597 614 611 600 633 645 611 670 654 636 700 608 699 654 614 689 665 680 689 629 584 574 664 644 580 647 647 645 618 637 662 649 628 677 666 628 639 578 629 608 645 610 592 629 583 580 623 637 673 589 654 588 600 652 633 598 601 
];
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
 6253 3309 2944
 9861 5533 4328
 4631 2265 2366
 29980 17931 12049
 5929 2534 3395
 8914 6259 2655
 5307 3112 2195
 8784 4813 3971
 748 478 270
 37669 22797 14872
 18 16 2
 387 312 75
 1650 1281 369
 11691 8938 2753
 1018 769 249
 922 673 249
 1432 1104 328
 3982 3018 964
 86150 53709 32441
 159 120 39
 1520 1199 321
 1139 866 273
 1822 1380 442
 6583 5121 1462
 104558 70856 33702
 2761 2197 564
 2828 2232 596
 6729 5556 1173
 174251 142739 31512
 66209 53766 12443
 19935635 16411910 3523725
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1 22 0 0
2 0 0 1
4 3 0 0
0 3 0 1
1 4 0 3
1 6 89 2
137 1 279 22
327 5 340 41
609 12 380 83
3625 6 579 147
19798 9 680 233
68126 28 856 375
148713 28 1027 544
255753 118 1197 838
338017 255 1429 1075
370466 520 1966 1704
316948 977 2562 2474
220626 1807 3518 3530
124246 3034 4780 4815
55629 4686 6462 6328
23556 7471 7910 7907
13534 11077 10092 9971
12447 16112 12774 12619
13902 21029 16168 16132
17367 26208 19446 19441
20022 30550 22764 22444
21762 37479 25813 25117
25110 42388 28844 28632
28251 50522 34059 33299
33002 56567 38898 37897
36826 60885 42278 41188
42288 66637 47644 47730
47049 72264 52932 52547
51365 76667 58110 56731
56855 80362 63919 63730
62078 84009 69007 68909
66622 86193 73395 72417
71274 89848 77766 77428
76416 93000 83876 81923
82358 96046 87746 87720
86167 98314 91869 91110
90279 100271 94278 93493
91634 101892 96511 95113
95290 103515 100304 98518
96541 104957 101829 100218
98602 105680 102312 101426
99494 105559 101716 101998
98308 103933 101921 100331
97431 102777 99778 100135
95875 99970 99070 96965
95578 97915 96652 96105
93402 95941 95244 93879
92298 93792 93716 92708
90955 92643 91982 90779
90750 91898 92150 90596
90961 91037 90597 89954
91171 91530 92386 90890
91310 93016 92185 91896
95862 95623 96607 95216
99500 99604 99932 98617
102809 102921 103794 102157
105629 105386 107475 105435
109186 108890 109238 108371
109134 109817 109581 108364
103666 103870 103936 103626
94653 94202 95473 94132
81743 81344 81787 81241
67445 67009 67389 66388
51863 51421 52383 51078
35418 35520 35992 35846
15825 15795 15663 15647
2159 2114 2012 2170
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
