A choreographer lines up n dancers of different heights. The routine is written as a string pattern of length n - 1 made of the letters U and D: pattern[i] == "U" means dancer i + 1 must be taller than dancer i, and "D" means dancer i + 1 must be shorter.
Return how many orderings of the n dancers follow the pattern, modulo 10**9 + 7. An empty pattern describes a single dancer, who has one ordering.
Examples
Input: pattern = "UD"
Output: 2
Explanation: with heights 1, 2, 3 the lineups are 1 3 2 and 2 3 1.
Input: pattern = "DDD"
Output: 1
Input: pattern = "UDU"
Output: 5
Constraints
0 <= len(pattern) <= 2000- every character is
UorD - Target complexity: O(n^2). Trying lineups is hopeless, and an O(n^3) table is too slow at the top size.
Goals
- Count permutations by tracking the rank of the last element among those placed so far
- See why only relative order matters when a new element is added
- Turn each O(n) transition into a running sum so the whole table costs O(n^2)