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 fk(x) as follows:

fk(x)={f(x)if k=1f(fk−1(x))if k>1

for all x between 0 and N−1, fk(x)=0 for some k.

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

Constraints

This is an output-only problem. Solve the problem for N=109.

Input Specification

There is no input.

Output Specification

Submit one integer in text: the number of arrays of size 109 satisfying the condition.

Sample Input

Copy
3

Sample Output

Copy
9

Explanation

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

The possible arrays are:

Copy
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