Arithmetic Equality

Given an integer $n$, find how many numbers of $n$ digits exist such that the sum of their digits and the product of their digits is equal.

Since the number may be big, print its answer modulo $10^9 + 7$.

Input

The only line of the input contains one integer, $n$ ($1 \leq n \leq 10^5$).

For tests worth 10 points, $1 \leq n \leq 6$.
For tests worth extra 30 points, $1 \leq n \leq 1\ 000$.

Output

The only line of the output will contain the required answer.

Example

stdin

2

stdout

1