# 0903. Valid Permutations for DI Sequence

<https://leetcode.com/problems/valid-permutations-for-di-sequence>

## Description

You are given a string `s` of length `n` where `s[i]` is either:

* `'D'` means decreasing, or
* `'I'` means increasing.

A permutation `perm` of `n + 1` integers of all the integers in the range `[0, n]` is called a **valid permutation** if for all valid `i`:

* If `s[i] == 'D'`, then `perm[i] > perm[i + 1]`, and
* If `s[i] == 'I'`, then `perm[i] < perm[i + 1]`.

Return *the number of **valid permutations*** `perm`. Since the answer may be large, return it **modulo** `109 + 7`.

**Example 1:**

```
**Input:** s = "DID"
**Output:** 5
**Explanation:** The 5 valid permutations of (0, 1, 2, 3) are:
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)
```

**Example 2:**

```
**Input:** s = "D"
**Output:** 1
```

**Constraints:**

* `n == s.length`
* `1 <= n <= 200`
* `s[i]` is either `'I'` or `'D'`.

## ac

```java
```