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}.