You are given two positive integers n and k.
A valid sequence is a sequence of k positive integers such that:
n.Return the number of valid sequences. Since the answer may be very large, return it modulo 109 + 7.
Two sequences are considered different if they differ at any index. For example, [1, 1, 2] and [1, 2, 1] are considered different sequences.
Example 1:
Input: n = 5, k = 3
Output: 3
Explanation:
The sequences of length k = 3 whose sum is 5 are:
| Sequence | Product | Parity |
|---|---|---|
[1, 1, 3] | 1 * 1 * 3 = 3 | Odd |
[1, 2, 2] | 1 * 2 * 2 = 4 | Even |
[2, 1, 2] | 2 * 1 * 2 = 4 | Even |
[2, 2, 1] | 2 * 2 * 1 = 4 | Even |
[1, 3, 1] | 1 * 3 * 1 = 3 | Odd |
[3, 1, 1] | 3 * 1 * 1 = 3 | Odd |
There are 3 sequences with an even product, thus the answer is 3.
Example 2:
Input: n = 3, k = 2
Output: 2
Explanation:
The sequences of length k = 2 whose sum is 3 are:
| Sequence | Product | Parity |
|---|---|---|
[1, 2] | 1 * 2 = 2 | Even |
[2, 1] | 2 * 1 = 2 | Even |
There are 2 sequences with an even product, thus the answer is 2.
Example 3:
Input: n = 5, k = 5
Output: 0
Explanation:
The only possible sequence of length k = 5 whose sum is 5 is [1, 1, 1, 1, 1], which has an odd product. Thus, the answer is 0.
Constraints:
1 <= n <= 5 * 1051 <= k <= n