In this problem, a function is any function that maps integers from 1 to n to integers from 1 to n.
For example, if n=3, one possible function is the function g defined as follows: g(1)=1, g(2)=3, and g(3)=1.
We will use the notation f^(j)(x) to denote applying a function f to the input x exactly j times in a row.
- for all valid x, f^(0)(x) = x
- for all valid x and j, f^(j+1)(x) = f^(j)(f(x))
We will now formally define several new notations.
- G(f,w) will be the set of all values f^(r)(x), where x is between 1 and n, inclusive, and r is greater than or equal to w.
- S(f,w) will be the size of G(f,w).
- Z(f) will be the minimum of S(f,w), taken over all nonnegative w.
- A(y) will be the set of all functions f such that Z(f) = y.
You are given the int n and an int k.
Compute and return the size of the set A(k), modulo 1,000,000,007.