You wish to create an array ~f(x)~ with the following properties:

1. The array has ~N~ elements.
2. Each element in the array is between ~0~ and ~N-1~.

We define ~f^k(x)~ as follows:

$$\displaystyle f^k(x) = \begin{cases} f(x) & \text{if }k = 1 \\ f(f^{k-1}(x)) & \text{if }k > 1 \end{cases}$$

for all ~x~ between ~0~ and ~N-1~, ~f^k(x) = 0~ for some ~k~.

Given an integer ~N~, what is the number of arrays that satisfy the above properties? Output the answer mod ~10^9+7~.

Constraints

This is an output-only problem. Solve the problem for ~N = 10^9~.

Input Specification

There is no input.

Output Specification

Submit one integer in text: the number of arrays of size ~10^9~ satisfying the condition.

Sample Input

3

Sample Output

9

Explanation

Note that you never actually have to solve the sample input.

The possible arrays are:

0 0 0
0 0 1
0 2 0
1 0 0
1 0 1
1 2 0
2 0 0
2 0 1
2 2 0