P1904.py

f = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 1965, 12911,
     14876, 12041, 11171, 7466, 2891, 10357, 13248, 7859, 5361, 13220, 2835, 309, 3144, 3453, 6597, 10050, 901, 10951,
     11852, 7057, 3163, 10220, 13383, 7857, 5494, 13351, 3099, 704, 3803, 4507, 8310, 12817, 5381, 2452, 7833, 10285,
     2372, 12657, 15029, 11940, 11223, 7417, 2894, 10311, 13205, 7770, 5229, 12999, 2482, 15481, 2217, 1952, 4169, 6121,
     10290, 665, 10955, 11620, 6829, 2703, 9532, 12235, 6021, 2510, 8531, 11041, 3826, 14867, 2947, 2068, 5015, 7083,
     12098, 3435, 15533, 3222, 3009, 6231, 9240, 15471, 8965, 8690, 1909, 10599, 12508, 7361, 4123, 11484, 15607, 11345,
     11206, 6805, 2265, 9070, 11335, 4659, 248, 4907, 5155, 10062, 15217, 9533, 9004, 2791, 11795, 14586, 10635, 9475,
     4364, 13839, 2457, 550, 3007, 3557, 6564, 10121, 939, 11060, 11999, 7313, 3566, 10879, 14445, 9578, 8277, 2109,
     10386, 12495, 7135, 3884, 11019, 14903, 10176, 9333, 3763, 13096, 1113, 14209, 15322, 13785, 13361, 11400, 9015,
     4669, 13684, 2607, 545, 3152, 3697, 6849, 10546, 1649, 12195, 13844, 10293, 8391, 2938, 11329, 14267, 9850, 8371,
     2475, 10846, 13321, 8421, 5996, 14417, 4667, 3338, 8005, 11343, 3602, 14945, 2801, 2000, 4801]


def new_fibonacci(n):
    if len(f) <= n:
        while len(f) - 1 < n:
            cal = f[-2] + f[-1]
            if cal >= 15746:
                cal = cal % 15746
            f.append(cal)
    return f[n]


if __name__ == '__main__':
    print(new_fibonacci(int(input())))