Problem Statement
You are given positive integers N and L. Count all sequences of positive integers with the following properties:
- The sequence is strictly increasing.
- The length of the sequence is L.
- No two consecutive elements share the same parity.
Return the number of these sequences, modulo 10^9 + 7.
Definition
- Class:
- AlternateParity
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int N, int L)
- (be sure your method is public)
Constraints
- N will be between 1 and 100,000, inclusive.
- L will be between 1 and N, inclusive.
Examples
6
6
Returns: 1
The only fitting sequence is {1, 2, 3, 4, 5, 6}.
5
2
Returns: 6
{1, 2}, {1, 4}, {2, 3}, {2, 5}, {3, 4}, and {4, 5} are the six valid sequences here.
12
4
Returns: 105
A few of these 105 sequences: {1, 2, 5, 10}, {2, 5, 8, 11}, {3, 6, 7, 8}, and {5, 8, 9, 12}.
12
5
Returns: 112
13
4
Returns: 140
13
5
Returns: 182
1
1
Returns: 1
2
1
Returns: 2
2
2
Returns: 1
3
1
Returns: 3
3
2
Returns: 2
3
3
Returns: 1
4
1
Returns: 4
4
2
Returns: 4
4
3
Returns: 2
4
4
Returns: 1
100000
49787
Returns: 894024743
99998
51234
Returns: 658225097
99999
49890
Returns: 243116830
99979
43211
Returns: 632771895
98768
97654
Returns: 469275672
98999
17
Returns: 43195670
19
4
Returns: 660
100000
1
Returns: 100000