An Easy Problem

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Text

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 Format

There is no input.

Output Format

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

Comments