For a sequence $(a_1, a_2, \dots, a_m)$, if for any $1 \le i \le m$, we have $1 \le a_i \le N$, we denote it as $\{a_i\}_m^N$.

For a sequence $\{a_i\}_m^N$, we can write it as an $m$-digit integer in base $N+1$: $(a_1 a_2 \dots a_m)_{N+1}$. We define the weight of this sequence as the value of $(a_1 a_2 \dots a_m)_{N+1}$ converted to base 10.

For a sequence $\{a_i\}_m^N$, if for any $1 \le i \le m-1$, we have $a_i < a_{i+1}$, or for any $1 \le i \le m-1$, we have $a_i > a_{i+1}$, then we call the sequence $\{a_i\}_m^N$ monotonic.

JYY dislikes monotonic sequences. He likes sequences $\{a_i\}_m^N$ that satisfy $m \le N$ and are non-monotonic.

JYY wants to know the sum of the weights of all sequences he likes for a given $N$. Since the sum of weights can be very large, JYY only needs to know the result modulo $1\,000\,000\,007$.

Input

The input contains a single integer $N$.

Output

Output a single integer representing the sum of the weights modulo $1\,000\,000\,007$.

Examples

Input 1

2

Output 1

12

Input 2

3

Output 2

1080

Input 3

4

Output 3

103460

Note

For the first example, all sequences JYY likes are: $11, 22$. Therefore, the required sum of weights is: $(11)_3 + (22)_3 = (12)_{10}$.

For the second example, all sequences with length at most $N$ are: $1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33, 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333$.

Among these, the non-monotonic sequences JYY likes are: $11, 22, 33, 111, 112, 113, 121, 122, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 322, 323, 331, 332, 333$.

Constraints

For 20% of the data, $N \le 8$; For 50% of the data, $N \le 2000$; For 70% of the data, $N \le 10^5$; For 100% of the data, $N \le 10^9$.