Многочлен

Задан многочлен вида

По степени многочлена n вычислите сумму его коэффициентов по модулю 9973 после раскрытия скобок и приведения подобных членов.

Входные данные

Одно целое число n (1 ≤ n ≤ 100) - степень многочлена.

Выходные данные

Вывести целое число, равное сумме коэффициентов многочлена по модулю 9973 после раскрытия скобок и приведения подобных членов (т.е. остаток от деления суммы коэффициентов на 9973).

Примеры