1
class Solution:
2
    def numPermsDISequence(self, s: str) -> int:
3
        n = len(s)
4
        dp = [[None for j in range(n - i + 1)] for i in range(n)]
5
        for j in range(n - 1, 0 - 1, -1):
6
            if s[j] == "I":
7
                if j == n - 1:
8
                    dp[j][0] = 1
9
                    dp[j][1] = 0
10
                else:
11
                    dp[j][n - j] = 0
12
                    for i in range((n - j) - 1, 0 - 1, -1):
13
                        dp[j][i] = dp[j + 1][i] + dp[j][i + 1]
14
            else:
15
                if j == n - 1:
16
                    dp[j][0] = 0
17
                    dp[j][1] = 1
18
                else:
19
                    dp[j][0] = 0
20
                    for i in range(1, n - j + 1):
21
                        dp[j][i] = dp[j + 1][i - 1] + dp[j][i - 1]
22
        return sum([dp[0][i] for i in range(n + 1)]) % (10**9 + 7)