Problem Statement
Given is a positive integer N.
Let S = { 0, 1, ..., N-1 }. All functions in this problem are functions defined on the set S with values from the set S.
Let f[t](x) denote the function f applied t times to the input x. In other words, f[1](x) is simply f(x), f[2](x) is f(f(x)), and so on.
Formally, f[0](x) = x and for all t, f[t+1](x) = f( f[t](x) ).
In addition to N, you are given another positive integer K. We are now interested in functions with the following property:
for all x in S: x + f[K](x) = N - 1
Count all such functions. Return their count modulo 10^9 + 7.
Definition
- Class:
- RepeatedApplication
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int N, int K)
- (be sure your method is public)
Notes
- The total number of functions on S is finite, so the return value is always well-defined.
Constraints
- N will be between 1 and 2,000, inclusive.
- K will be between 1 and 2,000, inclusive.
Examples
42
1
Returns: 1
There is clearly exactly one function f such that for all x from 0 to 41, inclusive, x + f(x) = 41.2
4
Returns: 0
For N = 2 we have S = {0, 1}. There are only four functions on this S: we have two options for the value of f(0) and two for the value of f(1). We can easily verify that none of the four functions have the desired property.5
2
Returns: 2
One of the two functions that have the desired property has the following values: f(0)=1, f(1)=4, f(2)=2, f(3)=0, and f(4)=3. We can easily verify that: 0 + f(f(0)) = 0 + f(1) = 0 + 4 = 4. 1 + f(f(1)) = 1 + f(4) = 1 + 3 = 4. 2 + f(f(2)) = 2 + f(2) = 2 + 2 = 4. 3 + f(f(3)) = 3 + f(0) = 3 + 1 = 4. 4 + f(f(4)) = 4 + f(3) = 4 + 0 = 4.7
4
Returns: 0
8
4
Returns: 48