<p>You are given a string <code>s</code> of length <code>n</code> where <code>s[i]</code> is either:</p>

<ul>
	<li><code>&#39;D&#39;</code> means decreasing, or</li>
	<li><code>&#39;I&#39;</code> means increasing.</li>
</ul>

<p>A permutation <code>perm</code> of <code>n + 1</code> integers of all the integers in the range <code>[0, n]</code> is called a <strong>valid permutation</strong> if for all valid <code>i</code>:</p>

<ul>
	<li>If <code>s[i] == &#39;D&#39;</code>, then <code>perm[i] &gt; perm[i + 1]</code>, and</li>
	<li>If <code>s[i] == &#39;I&#39;</code>, then <code>perm[i] &lt; perm[i + 1]</code>.</li>
</ul>

<p>Return <em>the number of <strong>valid permutations</strong> </em><code>perm</code>. Since the answer may be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;DID&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> 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)
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;D&quot;
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == s.length</code></li>
	<li><code>1 &lt;= n &lt;= 200</code></li>
	<li><code>s[i]</code> is either <code>&#39;I&#39;</code> or <code>&#39;D&#39;</code>.</li>
</ul>

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        # def _dfs(l_cnt, r_cnt, s):
        #     if not s:
        #         return 1
        #     if (s[0] == 'D' and l_cnt == 0) or (s[0] == 'I' and r_cnt == 0):
        #         return 0
            
        #     if (l_cnt, r_cnt, s) in mem:
        #         return mem[(l_cnt, r_cnt, s)]

        #     ans = 0
        #     if s[0] == 'D':
        #         for i in range(l_cnt):
        #             ans += _dfs(i, l_cnt - i - 1 + r_cnt, s[1:])
        #     else:
        #         for i in range(r_cnt):
        #             ans += _dfs(l_cnt + i, r_cnt - i - 1, s[1:])

        #     mem[(l_cnt, r_cnt, s)] = ans

        #     return ans 

        # n = len(s) + 1

        # mem = {}

        # return sum([_dfs(i, n - i - 1, s) for i in range(n)]) % (10**9 + 7)

        def fn(i, x):
            """Return number of valid permutation given x numbers smaller than previous one."""
            if i == n: 
                return 1

            if (i, x) in mem:
                return mem[(i, x)]

            ans = 0
            if s[i] == "D":
                if x == 0:                     
                    ans = 0  # cannot decrease
                else: 
                    ans = fn(i, x - 1) + fn(i + 1, x - 1)
            else:
                if x == len(s) - i: 
                    ans = 0  # cannot increase
                else:
                    ans = fn(i, x + 1) + fn(i + 1, x)
            
            mem[(i, x)] = ans
            return ans 

        n = len(s)
        mem = {}
        return sum(fn(0, x) for x in range(len(s) + 1)) % 1_000_000_007
31900