Lambda checks primality in a weird way. He checks the following two conditions.

• All the digits of the number in the decimal system are primes or one, namely 1, 2, 3, 5 or 7.
• It isn't a multiple of 2, 3, 5, 7, 11 or 47 (Why 47? I don't know).

In order to estimate the accuracy of his approach, he asks you to calculate the number of decimal integers of a specific length that satisfy the conditions.

Input

The first and only line contains an integer n, denoting the length of integers.

Output

The only line contains the answer modulo 9973.

Example

Input:
1

Output:
1

Input:
2

Output:
8

Input:
4

Output:
182

Input:
1000000000

Output:
4589

Constraints

1 <= n <= 10⁹
In 50% of testcases, n <= 100

Note: Data corrected and solutions rejudged. Sorry for inconvenience.

Warning: A naive solution won't terminate in 30s. And be careful with certain languages.