number-of-stable-subsequences

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code>.

A subsequence is stable if it does not contain three consecutive elements with the same parity when the subsequence is read in order (i.e., consecutive inside the subsequence).

Return the number of stable subsequences.

Since the answer may be too large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,3,5]

Output: 6

Explanation:

<ul>
	<li>Stable subsequences are <code>[1]</code>, <code>[3]</code>, <code>[5]</code>, <code>[1, 3]</code>, <code>[1, 5]</code>, and <code>[3, 5]</code>.</li>
	<li>Subsequence <code>[1, 3, 5]</code> is not stable because it contains three consecutive odd numbers. Thus, the answer is 6.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: nums = [2,3,4,2]

Output: 14

Explanation:

<ul>
	<li>The only subsequence that is not stable is <code>[2, 4, 2]</code>, which contains three consecutive even numbers.</li>
	<li>All other subsequences are stable. Thus, the answer is 14.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10​​​​​​​5</code></li>
</ul>