Count Positive Sequences with an Even Product

# Count Positive Sequences with an Even Product You are given positive integers `n` and `k`. Count the ordered sequences of exactly `k` positive integers whose sum is `n` and whose product is even. Return the count modulo `1000000007`. Two sequences are different if they differ at any position. Reordering unequal values can therefore produce a different sequence. ### Function `int countValidSequences(int n, int k)` ### Example 1 **Input:** `n = 6, k = 3` **Output:** `10` **Explanation:** The possible sequences consist of the three orderings of `[4, 1, 1]`, the six orderings of `[3, 2, 1]`, and `[2, 2, 2]`. All ten have an even product. ### Example 2 **Input:** `n = 8, k = 2` **Output:** `3` **Explanation:** The valid sequences are `[2, 6]`, `[4, 4]` and `[6, 2]`. The other positive pairs summing to `8` contain two odd values and have odd products. ### Constraints - `1 <= n <= 500000` - `1 <= k <= n` ### Clarifications - Every sequence element must be positive; zero is not allowed. - Count sequences with exactly `k` elements, not at most `k`. - The parity condition applies to the product, while the sum must equal `n` exactly. ### What a Strong Answer Covers - Counting ordered choices without merging distinct permutations. - Enforcing positivity, exact length and even-product conditions together. - Handling the full upper bound and returning a correctly normalized modular count.