Number of Stable Subsequences

Challenge Points: 30

Level: Hard

You are given an array nums.
You need to count how many subsequences can be formed such that no subsequence contains 3 numbers in a row that are all even or all odd.

A subsequence means we can choose elements in order, but they don’t have to be next to each other in the original array.

Since the total number of subsequences can be large, return the result modulo 10⁹ + 7.

Example 1:

Input: nums = [2, 6, 8]

Output: 6

Explanation:

All subsequences except [2, 6, 8] are valid because [2, 6, 8] has three even numbers in a row.

Example 2:

Input: nums = [1, 2, 1, 4]

Output: 15

Explanation:

The subsequence [1, 2, 4] is allowed because it does not contain three same-parity elements in a row. All subsequences are stable except the one [1, 1, 1].

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result