Triway Cup '19 Summer I - An Easy Problem

View as PDF
Submit solution
Points: 5
Time limit: 1.0s
Memory limit: 256M
Authors:
imaxblue, imaxred
Problem type

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

Comments