values that contains only the numbers 0, 1 and 2. Call a sequence a staircase if it is one or more 0s, followed by one or more 1s, followed by one or more 2s, and nothing else. For example, [0, 1, 2] and [0, 0, 1, 2, 2] are staircases, while [0, 2] and [0, 1, 2, 1] are not.
A subsequence is obtained by deleting some elements of the array without changing the order of the rest. Two subsequences are different if their sets of chosen indices differ.
Return the number of subsequences of values that are staircases, modulo 10⁹ + 7.values=[0, 0, 1, 2] → 3
The 1 and the 2 must be taken, and the zeros can be the first, the second or both: [0, 1, 2], [0, 1, 2] and [0, 0, 1, 2]. The answer is 3.
values=[1, 2, 0] → 0
The only 0 comes after the 1 and the 2, so no staircase can be formed: the answer is 0.
values=[0, 1, 1, 2, 2] → 9
A non-empty choice of the two 1s can be made in 3 ways, and the same goes for the two 2s: 3 · 3 = 9.
values=[0, 0, 1, 2]
3
Run checks the first 3 tests in your browser. Submit checks all 131 tests on the server, hidden ones included.