Count Subsequences That Move Between Positions

Problem Statement

You are given an array of n integers. A subsequence is defined as a sequence that can be derived from the array by deleting zero or more elements without changing the order of the remaining elements.

We define a "Valid Alternating Subsequence" as a subsequence where every adjacent pair of elements (a, b) satisfies the condition: (a + b) is odd. In other words, the subsequence must strictly alternate between even and odd numbers.

Your task is to implement a function countValidSubsequences(nums) that returns the total number of non-empty Valid Alternating Subsequences. Since the result can be very large, return it modulo 10^9 + 7.

Function Signature

def countValidSubsequences(nums: list[int]) -> int:

Constraints

• 1 <= n <= 10^5
• 0 <= nums[i] <= 10^9

Examples

Example 1: Input: nums = [1, 2, 3] Output: 6 Explanation: The valid subsequences are [1], [2], [3], [1, 2], [2, 3], [1, 2, 3]. Note that [1, 3] is invalid because 1+3 is even.

Example 2: Input: nums = [2, 4, 6] Output: 3 Explanation: The only valid subsequences are single-element subsequences: [2], [4], [6].

Edge Cases

• Arrays containing only even or only odd numbers.
• Arrays with duplicate values.
• Large input arrays (ensure O(n) complexity).