#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 5e3+10;
const int lcy = 1005060097;

int n;

int a[maxn] = { 0, 0, 1, 1, 1, 1, 6, 1, 1, 1, 8, 1, 8, 1, 10, 9, 1, 1, 12, 1, 10, 11, 14, 1, 12, 1, 16, 1, 12, 1, 42, 1, 1, 15, 20, 13, 14, 1, 22, 17, 14, 1, 54, 1, 16, 15, 26, 1, 20, 1, 28, 21, 18, 1, 30, 17, 16, 23, 32, 1, 60, 1, 34, 17, 1, 19, 78, 1, 22, 27, 74, 1, 18, 1, 40, 29, 24, 19, 90, 1, 22, 1, 44, 1, 76, 23, 46, 33, 20, 1, 90, 21, 28, 35, 50, 25, 36, 1, 52, 21, 30, 1, 114, 1, 22, 87, 56, 1, 32, 1, 106, 41, 24, 1, 126, 29, 34, 23, 62, 25, 96, 1, 64, 45, 36, 1, 114, 1, 1, 47, 122, 1, 108, 27, 70, 33, 26, 1, 150, 1, 100, 51, 74, 25, 26, 35, 76, 53, 42, 1, 162, 1, 28, 27, 134, 37, 124, 1, 82, 57, 38, 31, 84, 1, 46, 123, 86, 1, 120, 1, 154, 29, 48, 1, 186, 33, 28, 63, 92, 1, 120, 1, 154, 65, 32, 43, 198, 29, 52, 35, 170, 1, 68, 1, 100, 141, 54, 1, 162, 1, 34, 71, 104, 37, 156, 47, 106, 33, 30, 31, 366, 1, 58, 75, 110, 49, 36, 39, 112, 77, 140, 31, 234, 1, 40, 35, 116, 1, 172, 1, 202, 153, 38, 1, 186, 53, 64, 83, 194, 1, 168, 1, 124, 1, 66, 55, 258, 33, 40, 87, 128, 1, 148, 35, 130, 177, 1, 1, 270, 45, 160, 39, 134, 1, 168, 59, 214, 93, 72, 1, 234, 1, 34, 175, 140, 37, 204, 1, 142, 41, 152, 1, 294, 1, 76, 195, 218, 49, 42, 1, 250, 101, 78, 1, 306, 65, 46, 39, 152, 37, 220, 51, 154, 105, 36, 67, 234, 1, 172, 107, 266, 1, 192, 1, 160, 165, 84, 1, 330, 41, 70, 111, 254, 37, 86, 39, 166, 113, 50, 55, 534, 1, 88, 47, 170, 73, 208, 1, 172, 117, 200, 43, 258, 1, 52, 231, 176, 1, 252, 1, 274, 41, 44, 1, 366, 77, 94, 219, 182, 1, 180, 1, 184, 125, 196, 79, 378, 1, 40, 51, 314, 61, 268, 1, 274, 129, 56, 43, 294, 1, 220, 131, 194, 1, 132, 191, 196, 53, 102, 1, 618, 41, 58, 135, 200, 85, 204, 1, 202, 241, 42, 1, 414, 45, 106, 87, 314, 49, 240, 1, 346, 141, 108, 67, 306, 89, 46, 143, 302, 1, 540, 1, 214, 57, 62, 43, 438, 69, 112, 243, 362, 1, 44, 1, 334, 285, 114, 43, 450, 1, 208, 59, 314, 1, 316, 95, 226, 153, 72, 1, 330, 53, 118, 155, 230, 217, 264, 1, 232, 45, 260, 1, 690, 1, 46, 303, 236, 1, 232, 75, 394, 161, 68, 55, 486, 45, 244, 63, 242, 1, 312, 51, 244, 285, 126, 103, 246, 1, 70, 167, 410, 1, 348, 47, 346, 225, 48, 79, 510, 1, 130, 171, 254, 1, 216, 107, 358, 173, 132, 1, 786, 81, 1, 47, 260, 109, 364, 59, 394, 177, 236, 1, 378, 1, 136, 307, 266, 49, 288, 1, 442, 69, 268, 55, 546, 113, 76, 183, 272, 61, 300, 1, 274, 185, 50, 115, 798, 1, 142, 71, 386, 49, 312, 87, 280, 357, 144, 1, 402, 57, 256, 303, 284, 1, 396, 119, 286, 89, 80, 1, 870, 1, 268, 195, 434, 49, 74, 1, 292, 197, 320, 91, 594, 65, 82, 255, 296, 1, 412, 51, 490, 201, 54, 1, 414, 269, 154, 203, 410, 1, 336, 1, 454, 77, 156, 127, 618, 1, 52, 351, 506, 61, 288, 1, 310, 393, 248, 1, 630, 1, 340, 51, 314, 97, 328, 1, 316, 333, 162, 55, 810, 1, 88, 215, 320, 133, 444, 63, 442, 81, 134, 1, 654, 1, 316, 411, 434, 1, 90, 71, 442, 373, 168, 1, 666, 137, 58, 83, 494, 1, 780, 1, 334, 345, 92, 295, 474, 53, 172, 227, 554, 73, 384, 1, 340, 53, 174, 1, 690, 105, 292, 231, 470, 1, 316, 143, 346, 233, 60, 67, 1038, 1, 178, 267, 350, 145, 384, 59, 352, 237, 340, 1, 474, 57, 76, 447, 356, 109, 492, 1, 586, 89, 98, 55, 1014, 293, 184, 243, 362, 1, 300, 111, 364, 245, 186, 55, 738, 1, 280, 1, 602, 61, 508, 1, 370, 465, 56, 79, 522, 1, 400, 379, 554, 1, 408, 155, 376, 93, 332, 115, 762, 1, 64, 255, 506, 157, 364, 1, 382, 393, 320, 1, 774, 117, 196, 315, 386, 73, 260, 1, 958, 261, 198, 1, 546, 57, 106, 439, 392, 61, 900, 83, 514, 57, 66, 163, 798, 1, 202, 267, 650, 121, 288, 75, 400, 501, 204, 1, 1122, 65, 58, 99, 404, 85, 556, 347, 538, 273, 110, 1, 666, 1, 388, 275, 554, 169, 408, 63, 412, 301, 440, 1, 834, 1, 112, 423, 614, 1, 372, 1, 682, 281, 78, 67, 846, 173, 364, 59, 422, 1, 888, 1, 424, 285, 216, 175, 594, 129, 70, 287, 554, 61, 588, 1, 634, 345, 116, 1, 1158, 1, 460, 483, 434, 1, 60, 179, 436, 293, 412, 91, 1290, 81, 118, 107, 566, 133, 604, 1, 442, 297, 344, 1, 618, 1, 376, 555, 446, 1, 480, 135, 730, 93, 228, 67, 906, 185, 136, 447, 452, 61, 400, 71, 610, 505, 122, 187, 918, 1, 232, 111, 1106, 1, 448, 95, 460, 573, 234, 139, 594, 1, 376, 311, 464, 85, 996, 63, 466, 113, 62, 1, 1374, 69, 238, 315, 470, 361, 324, 1, 694, 317, 500, 1, 954, 65, 76, 399, 638, 1, 652, 87, 610, 321, 344, 1, 666, 197, 244, 483, 482, 145, 600, 1, 634, 117, 246, 199, 1338, 1, 130, 471, 794, 1, 248, 147, 490, 481, 78, 1, 990, 101, 520, 119, 494, 1, 528, 203, 634, 549, 412, 67, 1170, 1, 64, 335, 734, 205, 684, 1, 502, 65, 134, 343, 1014, 77, 256, 627, 506, 73, 352, 1, 826, 341, 428, 1, 1026, 425, 136, 123, 512, 1, 1140, 1, 754, 513, 1, 67, 654, 93, 262, 347, 842, 1, 552, 1, 694, 405, 484, 79, 1050, 1, 388, 351, 524, 157, 456, 395, 526, 353, 140, 1, 1446, 1, 268, 95, 674, 217, 528, 159, 532, 357, 560, 1, 738, 1, 376, 663, 698, 109, 732, 1, 874, 369, 84, 67, 1086, 69, 274, 363, 722, 97, 432, 71, 544, 365, 276, 451, 1098, 1, 82, 131, 890, 1, 1148, 1, 550, 681, 146, 1, 762, 165, 460, 371, 698, 1, 528, 407, 814, 69, 282, 1, 1626, 113, 148, 615, 560, 229, 484, 1, 730, 377, 464, 79, 1470, 1, 286, 135, 566, 73, 600, 1, 922, 549, 288, 115, 834, 233, 88, 383, 572, 85, 1260, 171, 574, 137, 368, 235, 1158, 69, 532, 387, 722, 1, 138, 1, 580, 1149, 294, 103, 1170, 81, 460, 71, 854, 1, 796, 239, 778, 393, 90, 175, 1350, 1, 298, 555, 590, 73, 624, 119, 742, 141, 620, 1, 1194, 177, 70, 735, 596, 1, 492, 71, 1402, 401, 158, 1, 1206, 245, 484, 403, 602, 121, 568, 1, 604, 405, 556, 247, 834, 89, 160, 583, 986, 181, 828, 1, 610, 249, 84, 1, 1662, 77, 640, 603, 794, 1, 396, 75, 616, 413, 312, 1, 1794, 1, 400, 147, 620, 445, 844, 1, 622, 681, 488, 91, 774, 125, 316, 771, 914, 73, 600, 1, 628, 149, 318, 187, 1626, 257, 166, 423, 794, 1, 1140, 111, 634, 425, 96, 463, 1278, 189, 322, 75, 1034, 73, 672, 87, 826, 597, 524, 1, 882, 1, 262, 703, 644, 1, 876, 263, 646, 393, 440, 1, 1878, 1, 508, 435, 650, 529, 98, 1, 862, 437, 520, 1, 1770, 1, 172, 495, 656, 1, 892, 419, 1066, 609, 74, 115, 906, 269, 604, 443, 662, 1, 1272, 1, 664, 77, 336, 79, 1698, 1, 100, 447, 1550, 1, 568, 75, 826, 825, 176, 199, 1350, 117, 700, 159, 890, 97, 736, 275, 676, 453, 342, 91, 834, 201, 178, 663, 680, 277, 924, 83, 994, 161, 476, 1, 1374, 77, 556, 1323, 686, 1, 432, 1, 1114, 461, 348, 1, 1386, 137, 76, 99, 890, 205, 1500, 1, 694, 465, 182, 283, 1494, 93, 352, 467, 1130, 121, 648, 207, 874, 525, 354, 139, 1410, 1, 472, 471, 704, 85, 556, 287, 874, 769, 140, 1, 2046, 101, 358, 167, 1034, 289, 744, 123, 712, 693, 740, 79, 978, 1, 106, 655, 878, 1, 1452, 1, 1594, 81, 188, 1, 1446, 581, 364, 483, 722, 1, 540, 143, 1054, 685, 366, 295, 1458, 1, 190, 471, 890, 1, 988, 1, 730, 897, 448, 79, 732, 1, 760, 491, 914, 457, 768, 299, 736, 173, 372, 127, 2130, 1, 88, 495, 974, 85, 624, 219, 742, 681, 572, 1, 1878, 1, 676, 531, 746, 1, 688, 1, 1210, 813, 378, 1, 1026, 521, 448, 503, 1094, 1, 1020, 99, 754, 177, 80, 607, 1518, 149, 592, 507, 1226, 1, 504, 107, 760, 933, 384, 79, 1938, 81, 520, 179, 764, 1, 1036, 87, 1114, 513, 200, 151, 1710, 1, 388, 835, 986, 313, 516, 83, 772, 101, 1340, 91, 1554, 1, 202, 951, 776, 469, 652, 1, 946, 753, 114, 1, 2094, 317, 394, 183, 962, 1, 1464, 231, 1030, 525, 596, 319, 954, 1, 82, 527, 1274, 1, 1068, 135, 790, 505, 206, 103, 1590, 1, 820, 723, 1154, 1, 456, 323, 1018, 533, 402, 235, 2298, 81, 208, 87, 800, 565, 1604, 1, 994, 753, 90, 1, 1098, 237, 406, 987, 1058, 1, 840, 1, 1846, 189, 628, 1, 1626, 545, 118, 783, 812, 1, 840, 1, 814, 545, 536, 139, 1638, 1, 652, 191, 1322, 241, 744, 95, 1006, 1005, 414, 1, 1722, 161, 628, 551, 824, 85, 1116, 659, 826, 89, 120, 115, 2094, 141, 748, 747, 830, 337, 504, 1, 832, 901, 860, 163, 1674, 1, 142, 615, 1034, 1, 1132, 1, 1354, 561, 488, 247, 1014, 93, 424, 787, 842, 97, 1584, 1, 844, 477, 426, 343, 1698, 249, 220, 567, 1370, 109, 708, 1, 1234, 1041, 86, 1, 1710, 1, 640, 251, 1034, 145, 888, 599, 856, 573, 772, 1, 1890, 89, 124, 575, 860, 349, 1644, 119, 862, 201, 656, 1, 2310, 1, 436, 771, 866, 169, 92, 511, 1402, 581, 438, 1, 1746, 353, 568, 203, 1142, 85, 1860, 1, 1114, 945, 126, 355, 1194, 1, 652, 843, 1274, 121, 912, 1, 880, 597, 444, 259, 1770, 1, 616, 591, 884, 85, 736, 359, 886, 793, 500, 91, 2550, 533, 448, 207, 890, 97, 808, 1, 1294, 597, 920, 151, 1170, 1, 232, 1671, 1094, 1, 1212, 1, 1450, 209, 264, 175, 2238, 365, 454, 603, 1082, 265, 540, 1, 1114, 605, 716, 367, 2418, 153, 130, 95, 1466, 1, 1228, 87, 910, 1113, 236, 103, 1242, 125, 1540, 611, 914, 1, 816, 99, 1198, 573, 462, 91, 2634, 1, 238, 855, 1334, 373, 684, 179, 922, 617, 608, 271, 1854, 117, 466, 675, 1178, 1, 1608, 1, 1114, 621, 468, 127, 1266, 737, 94, 623, 932, 181, 1980, 1, 1138, 105, 242, 379, 1878, 1, 472, 1011, 2018, 1, 508, 1, 940, 629, 844, 1, 1890, 1, 712, 519, 944, 277, 1276, 635, 1138, 849, 92, 1, 2142, 93, 748, 635, 950, 385, 984, 279, 1210, 221, 700, 1, 1914, 185, 544, 1167, 956, 1, 792, 107, 1546, 889, 248, 1, 2406, 389, 484, 99, 1394, 121, 1176, 131, 964, 645, 736, 571, 1314, 89, 250, 647, 1562, 1, 1908, 1, 970, 705, 138, 163, 2382, 285, 1000, 651, 974, 97, 252, 395, 1414, 933, 492, 1, 2418, 1, 94, 607, 980, 637, 1324, 123, 1282, 657, 740, 91, 1338, 165, 496, 1203, 986, 289, 888, 191, 1594, 101, 728, 1, 2634, 105, 544, 663, 1190, 1, 1620, 291, 994, 665, 96, 403, 1998, 1, 892, 531, 1610, 193, 1032, 1, 1000, 1845, 504, 1, 1194, 1, 142, 879, 2030, 1, 1356, 407, 1234, 233, 260, 91, 2886, 1, 508, 963, 1226, 673, 624, 1, 1012, 677, 1040, 91, 2034, 297, 568, 107, 1016, 1, 1372, 1, 2290, 681, 144, 127, 1386, 701, 514, 1099, 1022, 1, 1848, 171, 1024, 237, 916, 415, 2562, 113, 1, 687, 1226, 301, 748, 1, 1306, 1257, 266, 139, 2070, 101, 1060, 239, 1034, 1, 928, 815, 1036, 957, 812, 1, 2250, 129, 664, 695, 1274, 109, 1404, 99, 1042, 609, 692, 1, 2094, 1, 526, 1275, 1514, 1, 612, 1, 2230, 933, 528, 595, 2106, 425, 148, 243, 1052, 1, 2060, 203, 1054, 705, 272, 427, 1338, 93, 772, 931, 1706, 1, 1008, 1, 1534, 765, 534, 103, 2130, 177, 796, 1143, 1064, 205, 876, 143, 1066, 713, 592, 1, 3054, 1, 808, 107, 1394, 841, 1104, 1, 1072, 933, 1100, 1, 2178, 1, 100, 1887, 1274, 133, 1452, 315, 1282, 249, 278, 1, 2166, 437, 844, 723, 1370, 145, 696, 1, 1294, 1165, 546, 439, 2178, 209, 280, 251, 2438, 181, 1468, 95, 1090, 945, 146, 319, 1482, 1, 1120, 731, 1094, 97, 1848, 695, 1096, 1, 552, 211, 3138, 321, 154, 975, 1100, 445, 904, 1, 1594, 737, 608, 103, 2214, 1, 796, 795, 1106, 1, 960, 1, 2326, 1053, 988, 1, 1314, 449, 286, 743, 1112, 325, 2340, 1, 1450, 577, 156, 115, 2958, 149, 562, 747, 1802, 121, 648, 647, 1120, 1365, 844, 1, 2250, 1, 880, 111, 1358, 1, 2076, 455, 1126, 1209, 290, 187, 1530, 1, 568, 755, 1346, 769, 1008, 99, 1132, 261, 1160, 619, 2778, 105, 292, 1383, 1478, 1, 1012, 1, 1834, 761, 104, 1, 2286, 637, 574, 603, 1394, 97, 2040, 1, 1654, 765, 576, 463, 1554, 1, 568, 1231, 1850, 109, 1548, 1, 1354, 729, 728, 1, 2310, 141, 820, 1059, 1154, 97, 266, 467, 1156, 773, 582, 1, 4602, 1, 298, 267, 1466, 469, 1564, 339, 1402, 777, 740, 223, 1374, 125, 1036, 1003, 1166, 193, 1200, 155, 1882, 709, 908, 1, 2346, 473, 106, 1023, 1694, 1, 1860, 1, 1174, 1113, 302, 919, 2838, 1, 592, 111, 1394, 1, 1048, 195, 1534, 1437, 844, 1, 1602, 345, 880, 791, 1184, 157, 1596, 803, 1714, 273, 102, 127, 3390, 1, 598, 1275, 1190, 145, 648, 1, 1402, 1093, 1940, 1, 2394, 1, 166, 855, 1196, 685, 1612, 1, 1930, 801, 632, 1, 2406, 485, 604, 1059, 1562, 1, 1032, 1, 1204, 117, 606, 787, 2418, 113, 760, 1143, 1946, 1, 988, 147, 1474, 2193, 168, 1, 2958, 101, 1240, 279, 1754, 1, 1248, 123, 1216, 813, 612, 355, 1962, 593, 148, 815, 1220, 493, 2364, 1, 1450, 281, 908, 1, 3030, 357, 916, 1491, 1226, 1, 612, 111, 1450, 1069, 618, 235, 2466, 497, 316, 679, 1232, 1, 2580, 131, 1234, 825, 704, 775, 1674, 1, 622, 827, 2570, 361, 1272, 1, 1240, 645, 624, 1, 3282, 105, 784, 831, 1514, 205, 876, 971, 1618, 833, 320, 151, 3558, 101, 1108, 287, 1466, 505, 1144, 239, 1252, 1101, 630, 103, 1698, 1, 322, 1527, 1814, 133, 2292, 207, 2026, 113, 174, 367, 2526, 509, 904, 843, 1262, 241, 1800, 1, 1594, 845, 636, 127, 2538, 369, 112, 291, 2654, 1, 1708, 167, 1834, 1545, 326, 103, 1494, 1, 1300, 1363, 1490, 1, 1128, 515, 1534, 293, 952, 1, 3066, 1, 688, 1095, 1280, 997, 1044, 1, 1282, 857, 518, 211, 3390, 245, 646, 795, 1286, 169, 1320, 375, 2074, 861, 648, 115, 2466, 129, 688, 863, 1292, 1, 2700, 119, 1294, 777, 656, 871, 2598, 213, 652, 867, 2882, 1, 114, 1, 1300, 1581, 1004, 103, 2610, 137, 676, 299, 1304, 157, 2516, 527, 1306, 1233, 180, 1, 2790, 381, 658, 1195, 1310, 529, 1344, 1, 2566, 125, 1340, 1, 3138, 105, 106, 1407, 1658, 109, 1072, 251, 2122, 881, 824, 1, 2646, 821, 664, 303, 1322, 721, 2256, 159, 1324, 885, 666, 535, 1554, 1, 340, 887, 1562, 253, 2388, 387, 1330, 945, 116, 1, 2670, 1, 2140, 891, 1334, 1, 756, 863, 1558, 1429, 932, 175, 3810, 1, 184, 255, 1934, 133, 1804, 1, 1690, 1161, 992, 391, 1818, 1, 1036, 1635, 1634, 1, 1440, 1, 2170, 669, 678, 1, 2706, 905, 346, 1143, 1622, 1, 940, 111, 1954, 1185, 186, 547, 3342, 1, 682, 811, 2186, 1, 1392, 1, 1606, 1653, 1204, 643, 1842, 1, 844, 911, 1364, 397, 1836, 135, 1594, 129, 728, 1, 5334, 1, 688, 915, 1370, 553, 664, 719, 1372, 1293, 1400, 1, 2754, 225, 352, 975, 1376, 109, 1852, 1, 1786, 1473, 108, 1, 1674, 845, 1024, 923, 1994, 121, 2424, 263, 1384, 317, 696, 1075, 2778, 1, 190, 1263, 2234, 181, 2028, 107, 1666, 1177, 356, 1, 2790, 405, 1420, 131, 1754, 145, 1176, 563, 2014, 933, 992, 1, 2970, 1, 358, 1207, 1814, 901, 1884, 1, 1402, 321, 736, 1, 2814, 1, 706, 2379, 1658, 409, 720, 1, 2266, 941, 988, 127, 3714, 569, 268, 323, 1412, 1, 2940, 763, 1714, 945, 362, 139, 1914, 269, 1252, 1203, 2282, 169, 1248, 1, 1786, 1101, 714, 1, 3498, 185, 1048, 951, 1658, 1, 1156, 575, 1426, 1297, 122, 799, 3390, 1, 988, 327, 1430, 577, 2328, 1, 1432, 957, 2180, 1, 1674, 417, 196, 1743, 1436, 109, 1932, 171, 3178, 729, 368, 187, 2886, 149, 724, 1539, 1442, 1, 1020, 111, 1870, 965, 1276, 583, 3498, 1, 370, 135, 2330, 109, 1948, 275, 1450, 1761, 198, 1, 2862, 237, 1000, 971, 1454, 1, 1488, 1127, 1456, 693, 732, 1, 4146, 113, 784, 975, 1694, 973, 734, 1, 1462, 1561, 1076, 151, 2934, 117, 1036, 715, 2834, 1, 1288, 131, 2362, 981, 738, 427, 1986, 593, 376, 1383, 1850, 1, 3060, 191, 1474, 137, 152, 895, 2958, 429, 1132, 987, 1730, 241, 828, 1, 2134, 1797, 744, 1, 3522, 281, 916, 879, 1484, 1, 2636, 599, 1486, 1257, 920, 1, 3078, 1, 748, 995, 1490, 769, 1248, 243, 1492, 341, 1520, 283, 3930, 177, 382, 1815, 1496, 133, 1212, 111, 3058, 1001, 680, 115, 3006, 605, 1324, 119, 1502, 1, 1536, 1, 1798, 2373, 756, 607, 2034, 129, 112, 1311, 3326, 1, 2028, 155, 1954, 1065, 764, 439, 3030, 1, 1540, 1299, 1514, 1, 784, 147, 1834, 1013, 762, 247, 4314, 441, 388, 347, 1754, 613, 2724, 1, 1762, 1017, 920, 1, 2058, 197, 766, 2715, 1526, 289, 1560, 1, 1786, 141, 1348, 115, 3066, 977, 208, 1023, 1982, 781, 2340, 1, 1534, 1025, 392, 619, 4038, 1, 1132, 771, 2474, 121, 1028, 447, 1786, 1293, 774, 199, 1842, 1, 2104, 1399, 1814, 1, 2076, 623, 1546, 353, 210, 1, 4398, 293, 778, 1035, 2954, 625, 864, 183, 1552, 1037, 1060, 451, 3810, 137, 130, 927, 1556, 253, 2972, 1, 2506, 1353, 398, 295, 2106, 1205, 1084, 1043, 1562, 1, 2592, 1, 2254, 357, 1196, 1, 3138, 113, 760, 1671, 2522, 133, 1068, 255, 1570, 2625, 114, 1, 3150, 117, 1600, 359, 1574, 457, 1608, 959, 1978, 1053, 792, 115, 3090, 161, 214, 1055, 1886, 637, 2124, 875, 1582, 257, 1160, 139, 3750, 1, 1396, 1923, 1586, 1, 792, 1, 2554, 1693, 1168, 187, 3186, 153, 406, 363, 2294, 301, 3300, 1, 1834, 1065, 216, 1015, 1854, 1, 802, 1067, 3290, 1, 2568, 135, 1600, 1125, 1124, 163, 3858, 465, 154, 1503, 1604, 1, 1296, 647, 2314, 1073, 410, 1, 4566, 189, 1228, 819, 1610, 649, 1408, 1, 1612, 1341, 2540, 1, 2178, 305, 808, 1351, 1616, 469, 2172, 1, 3250, 369, 134, 115, 3966, 653, 814, 1467, 1622, 121, 1188, 471, 1624, 1365, 816, 1075, 3258, 209, 832, 371, 2042, 1, 2188, 1, 1630, 2889, 848, 1, 2202, 1, 1660, 1091, 2354, 265, 1416, 659, 1918, 149, 1132, 475, 4650, 1, 418, 1095, 1640, 157, 2324, 143, 2122, 1097, 1004, 211, 3294, 117, 826, 1155, 1898, 193, 1680, 743, 3622, 1101, 828, 127, 1914, 665, 136, 1759, 1994, 1, 2940, 1, 2074, 377, 1016, 667, 3894, 1, 832, 1107, 2666, 913, 768, 1, 1660, 2733, 834, 139, 4362, 1, 1216, 123, 2150, 1, 2236, 835, 1666, 1113, 270, 1, 3510, 1, 1168, 1563, 1670, 985, 1704, 119, 1672, 981, 1700, 271, 3354, 1, 736, 2031, 2414, 1, 1132, 215, 1954, 1121, 428, 487, 4038, 1109, 844, 383, 1970, 1, 2976, 1, 1684, 1437, 846, 679, 3114, 889, 430, 1127, 2714, 1, 2268, 1, 2434, 153, 228, 319, 3390, 141, 1720, 1419, 2018, 217, 936, 683, 1696, 1133, 1492, 1, 4818, 1, 118, 807, 1700, 1309, 2284, 123, 1702, 1593, 812, 199, 2454, 125, 1156, 2067, 2138, 1, 1488, 495, 3502, 389, 858, 1, 3426, 689, 1048, 1479, 1712, 277, 2580, 323, 1978, 1825, 140, 163, 3438, 173, 862, 155, 2762, 121, 2616, 1, 2074, 2085, 864, 499, 2322, 201, 1048, 1423, 1724, 325, 3276, 1091, 1726, 393, 440, 1, 4038, 869, 868, 1155, 2234, 697, 156, 1, 3262, 1157, 1760, 1, 3474, 1, 442, 2295, 1736, 1, 2332, 1, 2794, 1569, 880, 175, 2346, 165, 1324, 1483, 1994, 121, 3000, 1, 1744, 125, 1276, 1051, 4578, 329, 142, 1167, 2810, 1, 1408, 507, 1750, 2121, 824, 283, 4278, 1, 1540, 399, 2114, 145, 1528, 707, 1756, 1869, 882, 151, 3546, 1, 448, 1175, 2534, 1045, 2364, 1, 1762, 801, 1160, 511, 3534, 285, 886, 1467, 2018, 1, 972, 1, 2842, 1653, 888, 1, 4146, 1361, 748, 159, 2042, 1, 3660, 1, 3370, 1185, 452, 715, 2394, 1, 892, 1891, 2066, 121, 1464, 767, 1780, 1245, 1564, 1, 3570, 1, 1300, 1191, 2234, 517, 1356, 1043, 1786, 1473, 240, 127, 6798, 1, 1228, 407, 1790, 793, 1824, 123, 1792, 1197, 1820, 1, 2418, 1, 520, 2175, 2318, 229, 3132, 135, 2890, 889, 458, 1, 3606, 725, 1204, 1683, 2594, 121, 820, 291, 1804, 1205, 1256, 1387, 3618, 1, 928, 411, 2906, 181, 3428, 1, 2266, 2193, 146, 1, 2094, 989, 1840, 1563, 1814, 1, 1848, 155, 2074, 853, 912, 211, 5154, 1, 244, 1935, 2126, 733, 1464, 1, 2194, 1217, 2408, 343, 3654, 1, 916, 735, 1826, 529, 1552, 131, 2122, 1221, 1388, 295, 3546, 1097, 466, 1527, 2102, 1, 3780, 531, 1834, 897, 246, 739, 4398, 213, 1612, 1227, 2954, 1, 864, 1, 2374, 1525, 924, 1, 3690, 297, 1072, 419, 2654, 157, 2476, 1211, 2194, 1233, 470, 919, 3870, 1, 1348, 1235, 1850, 745, 2832, 1, 1852, 165, 1240, 1, 3714, 537, 472, 3015, 2234, 349, 1492, 1, 4066, 1241, 158, 127, 3726, 749, 934, 1083, 2402, 1, 3192, 1, 1864, 1605, 1276, 175, 2178, 1, 250, 1743, 3002, 973, 2508, 1, 1870, 1305, 476, 139, 4902, 1, 2740, 1539, 1874, 217, 876, 1439, 1876, 1253, 942, 187, 3762, 153, 1144, 167, 1880, 757, 2524, 303, 1882, 2001, 1136, 1, 3438, 125, 946, 2283, 2714, 1, 1920, 1, 3790, 429, 1268, 355, 4434, 177, 124, 1263, 1892, 1, 2940, 219, 2170, 1705, 968, 763, 3798, 549, 952, 431, 3050, 241, 1648, 1, 2734, 3117, 1384, 1, 2562, 161, 880, 2023, 1904, 1, 2556, 767, 2458, 129, 944, 307, 5406, 141, 958, 1563, 1910, 1465, 1044, 359, 2230, 1621, 1940, 1, 4578, 1, 256, 855, 1916, 133, 3372, 555, 3082, 1281, 488, 1, 2214, 1205, 1684, 1283, 2282, 361, 2328, 191, 2314, 1117, 966, 775, 3858, 1, 940, 1287, 3638, 1, 1548, 1, 2194, 2337, 258, 943, 3870, 245, 1960, 843, 1934, 1, 3048, 779, 1936, 1293, 972, 127, 4050, 129, 154, 1295, 2426, 157, 3324, 1, 2794, 441, 1412, 1, 3894, 365, 976, 3411, 2234, 193, 260, 1, 3130, 1301, 1708, 247, 4746, 1145, 496, 443, 1952, 565, 3380, 131, 1954, 1305, 126, 1279, 3774, 1, 982, 1307, 3866, 1, 1992, 1015, 2326, 1125, 1484, 1, 3930, 1, 1180, 1311, 2234, 1, 1576, 183, 2458, 2985, 500, 1, 5574, 1, 988, 867, 2834, 793, 1608, 159, 2542, 1773, 2000, 571, 2274, 1, 916, 2391, 1976, 1, 3732, 371, 2290, 449, 808, 127, 3966, 1517, 1324, 1323, 1982, 145, 2520, 251, 2854, 1325, 996, 1243, 3978, 1, 160, 131, 3194, 373, 2668, 167, 1990, 1641, 1208, 139, 3582, 197, 2020, 1331, 2570, 577, 1728, 803, 1996, 453, 1002, 1, 7530, 321, 508, 1335, 2000, 1189, 1324, 579, 2002, 1633, 158, 1, 4638, 1, 2716, 1395, 2006, 1, 2040, 231, 3226, 2133, 1388, 1, 2706, 1313, 268, 1807, 2282, 1, 4140, 1, 2014, 177, 512, 967, 4902, 1, 1372, 1731, 4034, 169, 1168, 147, 2020, 2445, 1014, 379, 4050, 585, 1468, 459, 2294, 325, 2716, 815, 2914, 1713, 848, 1, 2346, 1, 1018, 2155, 2030, 817, 2064, 1, 2032, 981, 3140, 163, 4074, 257, 160, 2463, 2414, 133, 1632, 327, 4138, 1689, 518, 1, 5334, 189, 1024, 179, 2042, 1, 3264, 1103, 2554, 1365, 1026, 1195, 2754, 129, 1240, 1671, 3290, 1, 3588, 1, 2386, 2625, 1, 259, 4110, 1, 1360, 1371, 2954, 385, 936, 827, 2056, 1373, 1492, 595, 5826, 1, 274, 467, 2474, 829, 2764, 203, 2362, 1377, 1496, 331, 2778, 997, 1036, 1923, 2066, 1, 1680, 1, 4510, 261, 1038, 1, 4938, 833, 1048, 2199, 2072, 1, 3060, 143, 2458, 1385, 1024, 835, 4158, 893, 1432, 471, 2402, 601, 2112, 1, 2374, 2517, 1044, 1, 3906, 1, 1300, 1759, 2084, 205, 2796, 1235, 2086, 473, 530, 391, 5910, 141, 1828, 1875, 2090, 193, 924, 1, 2092, 2221, 3020, 151, 4890, 137, 532, 1191, 3878, 133, 2812, 131, 3370, 1953, 164, 607, 2826, 845, 1054, 1403, 2102, 841, 3288, 1, 2710, 477, 1056, 847, 4218, 609, 280, 1743, 3386, 1, 1528, 395, 2386, 2553, 968, 1, 4902, 1, 2140, 1219, 2114, 145, 1968, 195, 2116, 1413, 1852, 1, 4410, 1, 538, 1815, 2426, 1621, 2844, 243, 2650, 185, 1268, 1, 5550, 1, 1066, 2571, 2738, 169, 1152, 615, 2554, 1909, 1068, 1, 4266, 1217, 1024, 1023, 2132, 1, 4380, 1, 2134, 1737, 1028, 859, 2454, 269, 1612, 1427, 4658, 1, 1848, 1, 2140, 925, 1074, 1099, 4938, 401, 1552, 1431, 2144, 1, 2916, 863, 2146, 1433, 132, 1, 7806, 621, 1408, 135, 2546, 865, 2184, 1, 3094, 1437, 1420, 883, 2898, 345, 286, 3759, 2156, 133, 2892, 171, 3466, 489, 1088, 247, 4326, 869, 1564, 1443, 2594, 625, 1224, 179, 2164, 2013, 1436, 199, 5658, 1, 550, 991, 3482, 133, 2908, 627, 2794, 2625, 288, 1, 2922, 1, 3340, 1451, 2714, 145, 2208, 1415, 2458, 1029, 1092, 1, 5010, 249, 274, 1455, 3134, 1357, 1744, 1, 2182, 1457, 1580, 139, 4374, 1, 1096, 1515, 2474, 409, 3248, 275, 4270, 1773, 1098, 1, 2190, 633, 556, 1463, 2822, 181, 4500, 351, 3154, 497, 170, 883, 5118, 149, 1102, 3291, 3530, 1, 1188, 215, 2200, 2661, 1924, 1, 4410, 137, 904, 191, 2510, 1069, 2956, 887, 2206, 1977, 992, 1, 4590, 413, 1108, 1475, 2210, 889, 1824, 639, 2212, 501, 3140, 1, 5370, 1, 1336, 1815, 2216, 253, 1452, 147, 3562, 2353, 294, 943, 4446, 893, 1114, 963, 3194, 217, 3768, 1, 2224, 1485, 1676, 1699, 3954, 1, 172, 1487, 2570, 1, 4188, 135, 2674, 1449, 566, 1, 4470, 357, 2260, 1491, 2594, 1, 976, 1295, 4174, 1493, 1122, 151, 6330, 281, 1072, 1287, 2240, 205, 3004, 159, 2242, 1497, 1712, 1, 2574, 1, 1516, 3579, 2246, 649, 3288, 1, 3610, 509, 1128, 1, 5874, 1265, 298, 1503, 2810, 421, 1800, 651, 2254, 1897, 572, 1327, 4518, 1, 1492, 195, 4562, 361, 1824, 1, 2554, 3933, 1134, 1, 3042, 1, 1636, 2103, 4118, 1, 3876, 207, 2578, 513, 300, 655, 6414, 221, 1708, 1515, 2270, 913, 1368, 363, 2272, 1941, 2300, 259, 4554, 1217, 136, 1575, 2276, 1, 3052, 1, 4186, 1833, 578, 187, 4086, 917, 1564, 1843, 2570, 145, 3600, 1, 2284, 197, 1996, 1483, 4578, 1, 580, 1527, 3674, 661, 1828, 287, 2290, 1873, 968, 223, 5982, 261, 2320, 519, 2618, 1, 2328, 1751, 2296, 2133, 1492, 367, 4482, 1, 1120, 1535, 2300, 925, 3084, 1, 2722, 1321, 1016, 151, 5478, 1, 1156, 2787, 2594, 289, 522, 431, 3706, 1869, 1158, 667, 4626, 1433, 586, 263, 2312, 181, 6900, 1, 2314, 1905, 306, 163, 3114, 669, 1672, 1547, 3722, 433, 2352, 155, 3334, 1605, 1564, 1, 4650, 1, 1300, 3423, 2990, 1, 1516, 935, 2698, 1553, 1400, 1, 5334, 1, 1168, 1107, 2906, 1345, 2008, 1, 2794, 1557, 2360, 139, 4458, 1, 1168, 2823, 2336, 373, 3132, 1091, 3754, 201, 138, 1, 5406, 941, 2044, 1563, 2342, 1, 2880, 183, 2344, 2485, 1176, 943, 5682, 153, 310, 531, 5102, 1, 3948, 375, 2350, 2841, 596, 1255, 2682, 165, 1540, 1571, 2354, 1, 1896, 947, 2938, 533, 1772, 295, 6666, 681, 1048, 1575, 2360, 1333, 1884, 143, 3394, 2113, 1400, 1, 4734, 1, 1186, 1099, 2834, 193, 2400, 1, 4774, 1989, 2068, 1, 3186, 953, 166, 1583, 2750, 685, 4860, 443, 2374, 1017, 602, 1471, 6198, 149, 1192, 1587, 2810, 1, 960, 147, 2380, 2877, 1544, 139, 5658, 1, 3016, 539, 2384, 445, 3196, 959, 2386, 2529, 182, 271, 4950, 381, 1198, 1915, 4442, 217, 2424, 299, 2392, 141, 2420, 691, 4794, 1, 928, 3855, 2396, 1, 3212, 1, 3850, 1601, 608, 1, 5574, 1829, 1804, 1083, 2402, 1, 1960, 1, 2404, 1605, 1206, 967, 2754, 953, 610, 2551, 4766, 301, 3228, 1, 2746, 1665, 1168, 1, 5838, 141, 2440, 1611, 2414, 1225, 1296, 219, 2854, 1613, 1652, 451, 8994, 1, 184, 207, 2420, 973, 4124, 699, 2722, 1617, 1748, 151, 3258, 197, 2116, 3795, 2426, 169, 2088, 387, 2794, 1149, 1218, 235, 4866, 977, 616, 1623, 3494, 157, 2460, 1, 4210, 1625, 276, 1855, 4878, 189, 1222, 551, 3914, 1, 3768, 455, 2440, 2181, 1604, 1, 3282, 1169, 1444, 1631, 2444, 277, 4236, 983, 3514, 209, 1160, 1, 6918, 141, 1228, 2595, 2450, 1585, 1044, 143, 2782, 2013, 1600, 199, 5658, 1, 622, 1695, 3158, 709, 3292, 1, 3946, 1641, 324, 1, 4494, 989, 1234, 2283, 2462, 1, 4152, 1159, 2854, 557, 1236, 223, 4938, 393, 1312, 1983, 4790, 1, 1968, 1, 2470, 4281, 626, 1, 4950, 461, 3460, 143, 3554, 1, 2128, 1391, 2476, 2109, 1242, 151, 4410, 1, 628, 2215, 2480, 997, 4644, 1, 2794, 1041, 1376, 163, 4974, 717, 1696, 3003, 3098, 1, 1080, 1, 5398, 1661, 1868, 1, 4986, 225, 328, 1423, 2942, 397, 5100, 311, 2794, 2313, 1496, 1003, 3354, 1, 1612, 1667, 4010, 1153, 2232, 1, 3214, 1389, 1254, 283, 5802, 1, 634};
int main() {
	freopen("functiona.in", "r", stdin);
	freopen("functiona.out", "w", stdout);
	scanf("%d", &n);
	int tot = 0;
	for(int i = 1; i <= n; i++) {
		tot += a[i];
		tot %= lcy;
	}
	printf("%d\n", tot);
}