This is Jono's last task he is setting as a trainer. So he made a very haha funny task:

Let $\overline{XY}$ be $X$ and $Y$ written together as a number. For example, if $X = 12$ and $Y = 34$, then $\overline{XY} = 1234$. We can extend this notation to 3 or more concatenations, e.g. $\overline{XYXY} = 12341234$.

Let $A$ be Jono's favorite 2-digit number and $B$ be Jono's favorite 3-digit number. Given an integer $N$, compute ${\underbrace{\overline{AA \cdots A}}_{N \text{ times}}}^{\underbrace{\overline{ABAB \cdots AB}}_{N \text{ times}}}$ modulo $10^9 + 7$.

For example, if $N = 2$, you should compute ${\overline{AA}}^{\overline{ABAB}}$.

Input

The input consists of an integer $N$.

Output

Output the result modulo $10^9 + 7$.

Constraints

$1 \le N \le 10^{6}$