Polynomial

Given a polynomial

Given the degree of a polynomial n, calculate the sum of its coefficients modulo 9973 after opening the brackets and reducing such terms.

Input

One integer n (1 ≤ n ≤ 100) - the degree of the polynom.

Output

Print an integer equal to the sum of the coefficients of the polynomial modulo 9973 after opening the brackets and reducing such terms (i.e. the remainder of dividing the sum of the coefficients by 9973).

Examples