## LPRIME - Primes of Lambda

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 <= 109
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. Oleg: 2009-12-29 13:31:39 thanks, Lordxfastx, nice problem. Last edit: 2010-01-06 09:29:10