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
1
1
Returns: 1
1
2
Returns: 1
1
3
Returns: 1
1
4
Returns: 1
1
5
Returns: 1
1
6
Returns: 1
2
1
Returns: 1
2
2
Returns: 0
2
3
Returns: 1
2
4
Returns: 0
2
5
Returns: 1
2
6
Returns: 0
2
63
Returns: 1
3
1
Returns: 1
3
2
Returns: 0
3
3
Returns: 1
3
4
Returns: 0
3
5
Returns: 1
3
6
Returns: 0
3
8
Returns: 0
3
1069
Returns: 1
4
1
Returns: 1
4
2
Returns: 2
4
3
Returns: 1
4
4
Returns: 0
4
5
Returns: 1
4
6
Returns: 2
5
1
Returns: 1
5
2
Returns: 2
5
3
Returns: 1
5
4
Returns: 0
5
5
Returns: 1
5
6
Returns: 2
6
1
Returns: 1
6
2
Returns: 0
6
3
Returns: 9
6
4
Returns: 0
6
5
Returns: 1
6
6
Returns: 0
9
363
Returns: 33
12
14
Returns: 120
13
11
Returns: 1
14
1012
Returns: 0
15
4
Returns: 0
26
2
Returns: 0
31
1
Returns: 1
37
6
Returns: 935053234
59
1071
Returns: 829362404
80
10
Returns: 986227204
108
62
Returns: 607650842
127
5
Returns: 113322464
137
26
Returns: 637003322
166
1130
Returns: 0
188
3
Returns: 762514731
369
112
Returns: 0
453
8
Returns: 0
502
1899
Returns: 854848701
553
503
Returns: 1
616
638
Returns: 358276785
726
1136
Returns: 0
1013
218
Returns: 542825594
1365
268
Returns: 0
1471
756
Returns: 0
1900
7
Returns: 600064923
1900
14
Returns: 29545310
1909
31
Returns: 670689160
1910
1976
Returns: 0
1913
7
Returns: 864906344
1928
1966
Returns: 526159502
1942
12
Returns: 0
1945
1903
Returns: 257515141
1950
1979
Returns: 1
1952
2
Returns: 800294781
1952
1837
Returns: 241772777
1959
57
Returns: 589988788
1962
1911
Returns: 770343363
1977
43
Returns: 905566222
1979
7
Returns: 347088868
9
17
Returns: 1