pattern of length n made of the letters I and D. Line up all the integers from 0 to n, each exactly once, so that the line follows the pattern: if pattern[i] is I, the number at position i + 1 is greater than the number at position i, and if it is D, it is smaller.
How many such lineups exist? The count can be huge, so return it modulo 10⁹ + 7.pattern='ID' → 2
The numbers 0, 1, 2 must be arranged with the middle one above both neighbours: only (0, 2, 1) and (1, 2, 0) work.
pattern='DDI' → 3
The first three numbers fall and the last one is above the third. The third must be 0, which leaves (3, 2, 0, 1), (3, 1, 0, 2) and (2, 1, 0, 3).
pattern='III' → 1
Every number is above the one before it, so only the ascending order fits.
pattern.length ≤ 200pattern[i] is I or Dpattern='ID'
2
Run checks the first 3 tests in your browser. Submit checks all 250 tests on the server, hidden ones included.