We are given S, a length n string of characters from the set {'D', 'I'}. (These letters stand for "decreasing" and "increasing".)
A valid permutation is a permutation P[0], P[1], ..., P[n] of integers {0, 1, ..., n}, such that for all i:

If S[i] == 'D', then P[i] > P[i+1], and;
If S[i] == 'I', then P[i] < P[i+1].

How many valid permutations are there?  Since the answer may be large, return your answer modulo 10^9 + 7.
 
Example 1:
Input: "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)

 
Note:

1 <= S.length <= 200
S consists only of characters from the set {'D', 'I'}.

Difficulty: interview

Starter code:

class Solution:
    def numPermsDISequence(self, S: str) -> int:
        

Solutions:
class Solution:
    def numPermsDISequence(self, S):
        dp = [1] * (len(S) + 1)
        for a, b in zip('I' + S, S):
            dp = list(itertools.accumulate(dp[:-1] if a == b else dp[-1:0:-1]))
        return dp[0] % (10**9 + 7)


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        n = len(S) + 1
        dp = [[0] * (n + 1) for _ in range(n+1)]
        dp[1][0] = 1
        MOD = 10**9 + 7
        for i in range(2,n+1):
            p = [0] + list(itertools.accumulate(dp[i-1]))
            
            for j in range(i):
                L,R = None,None
                if S[i-2] == 'D': #decreasing
                    L = j
                    R = i - 2
                
                else: #increasing
                    L = 0
                    R = j - 1
                
                dp[i][j] = (p[R+1] - p[L])% MOD
                dp[i][j] %= MOD

        return sum(dp[n]) % MOD


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        n = len(S) + 1
        dp = [[0] * (n + 1) for _ in range(n+1)]
        dp[1][0] = 1
        MOD = 10**9 + 7
        for i in range(2,n+1):
            p = [0] + list(itertools.accumulate(dp[i-1]))
            
            for j in range(i):
                L,R = None,None
                if S[i-2] == 'D': #decreasing
                    L = j
                    R = i - 2
                
                else: #increasing
                    L = 0
                    R = j - 1
                
                dp[i][j] = (p[R+1] - p[L])% MOD
                dp[i][j] %= MOD

        res = 0
        for i in dp[n]:
            res += i
            res %= MOD
        return res


from functools import lru_cache

class Solution:
    def numPermsDISequence(self, S):
        MOD = 10**9 + 7
        N = len(S)

        @lru_cache(None)
        def dp(i, j):
            # How many ways to place P_i with relative rank j?
            if not (0 <= j <= i):
                return 0
            if i == 0:
                return 1
            elif S[i-1] == 'D':
                return (dp(i - 1, j) + dp(i, j + 1)) % MOD
            else:
                return (dp(i-1, j - 1) + dp(i, j - 1)) % MOD

        return sum(dp(N, j) for j in range(N+1)) % MOD

class Solution:
    def numPermsDISequence(self, S):
        MOD = 10**9 + 7
        N = len(S)

        @lru_cache(None)
        def dp(i, j):
            # How many ways to place P_i with relative rank j?
            if not(0 <= j <= i):
                return 0
            if i == 0:
                return 1
            elif S[i-1] == 'D':
                return (dp(i, j+1) + dp(i-1, j)) % MOD
            else:
                return (dp(i, j-1) + dp(i-1, j-1)) % MOD

        return sum(dp(N, j) for j in range(N+1)) % MOD

class Solution:
    def numPermsDISequence(self, S: str) -> int:
        from functools import lru_cache
        MOD = 10**9 + 7
        N = len(S)
        
        @lru_cache(None)
        def search(i, j):
            
            if not 0 <= j <= i:
                return 0
            
            if i == 0:
                return 1
            
            if S[i-1] == 'D':
                return (search(i, j+1) + search(i-1, j)) % MOD
            else:
                return (search(i, j-1) + search(i-1, j-1)) % MOD
            
        
        return sum(search(N, j) for j in range(len(S)+1)) % MOD

from functools import lru_cache


class Solution:
    def numPermsDISequence(self, S):
        MOD = 10**9 + 7
        N = len(S)

        @lru_cache(None)
        def dp(i, j):
            # How many ways to place P_i with relative rank j?
            if not(0 <= j <= i):
                return 0
            if i == 0:
                return 1
            elif S[i-1] == 'D':
                return (dp(i, j+1) + dp(i-1, j)) % MOD
            else:
                return (dp(i, j-1) + dp(i-1, j-1)) % MOD

        return sum(dp(N, j) for j in range(N+1)) % MOD


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        MOD = 10**9 + 7
        N = len(S)
        
        dp = [[0]*(N+1) for _ in range(N+1)]
        
        def solve(i, j):
            if not ( 0 <= j <= i):
                return 0 
            
            if dp[i][j]:
                return dp[i][j]
            
            if i == 0:
                return 1
            if S[i-1] == 'D':
                dp[i][j] = (solve(i, j-1) + solve(i-1, j-1))  % MOD
            else:
                dp[i][j] = (solve(i, j+1) + solve(i-1, j)) % MOD  
            
            return dp[i][j]
       
        return sum(solve(N, j) for j in range(N+1)) % MOD
            
            
            
         
        
        
        


from functools import lru_cache


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        MOD = 10 ** 9 + 7
        
        @lru_cache(None)
        def presum(n, last):
            if last == 0:
                return 0
            return DP(n, last - 1) + presum(n, last - 1)

        @lru_cache(None)
        def DP(n, last):
            if n == 0:
                return 1
            if S[n - 1] == 'D':
                return (presum(n - 1, n) - presum(n - 1, last)) % MOD
            else:
                return presum(n - 1, last) % MOD

        return sum(
            DP(len(S), i)
            for i in range(len(S) + 1)
        ) % MOD


from functools import lru_cache


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        MOD = 10 ** 9 + 7
        
        @lru_cache(None)
        def presum(n, last):
            if last == 0:
                return 0
            return DP(n, last - 1) + presum(n, last - 1)

        @lru_cache(None)
        def DP(n, last):
            if n == 0:
                return 1
            if S[n - 1] == 'D':
                return (presum(n - 1, n) - presum(n - 1, last)) % MOD
            else:
                return presum(n - 1, last) % MOD

        return presum(len(S), len(S) + 1) % MOD


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        dp = [1] * (len(S)+1)
        
        for a , b in zip('I'+S, S):
            dp = list(itertools.accumulate(dp[:-1] if a == b else dp[-1:0:-1]))
        
        return dp[0] % (10**9+7)


from functools import lru_cache

class Solution:
    def numPermsDISequence(self, S):
        MOD = 10**9 + 7
        N = len(S)

        @lru_cache(None)
        def dp(i, j):
            # How many ways to place P_i with relative rank j?
            if not(0 <= j <= i):
                return 0
            if i == 0:
                return 1
            elif S[i-1] == 'D':
                return (dp(i, j+1) + dp(i-1, j)) % MOD
            else:
                return (dp(i, j-1) + dp(i-1, j-1)) % MOD

        return sum(dp(N, j) for j in range(N+1)) % MOD

from functools import lru_cache

class Solution:
    def numPermsDISequence(self, S: str) -> int:

        MOD = 10**9 + 7
        N = len(S)

        @lru_cache(None)
        def dp(i, j):
            # How many ways to place P_i with relative rank j?
            if not(0 <= j <= i):
                return 0
            if i == 0:
                return 1
            elif S[i-1] == 'D':
                return (dp(i, j+1) + dp(i-1, j)) % MOD
            else:
                return (dp(i, j-1) + dp(i-1, j-1)) % MOD

        return sum(dp(N, j) for j in range(N+1)) % MOD

class Solution:
    def numPermsDISequence(self, S: str) -> int:
        MOD = 10**9+7
        n = len(S)
        
        @lru_cache(None)
        def dp(i, j):
            if not (0 <= j <= i):
                return 0
            if i == 0:
                return 1
            elif S[i-1] == 'D':
                return (dp(i, j+1)+ dp(i-1, j)) % MOD
            else:
                return (dp(i, j-1)+dp(i-1, j-1)) % MOD
        
        return sum(dp(n, j) for j in range(n+1)) % MOD


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        n = len(S)
        MOD = 10 ** 9 + 7

        dp = [[0]*(n+1) for _ in range(n+1)]

        dp[0][0] = 1

        for i in range(1, n+1):
            for j in range(i+1):
                if S[i-1] == 'D':
                    dp[i][j] = sum(dp[i-1][j:i] + [0]) % MOD
                else:
                    dp[i][j] = sum(dp[i-1][:j] + [0]) % MOD
        return sum(dp[-1]) % MOD

class Solution:
    def numPermsDISequence(self, S: str) -> int:
        d = [0] * (len(S) + 1)
        d[0] = 1
        for i,c in enumerate(S):
            if c == 'D':
                for j in range(i-1,-1,-1):
                    d[j] += d[j+1]
            else:
                for j in range(1,i+1):
                    d[j] += d[j-1]
                for j in range(i+1,0,-1):
                    d[j] = d[j-1]
                d[0] = 0
        return sum(d) % 1000000007

class Solution:
    def numPermsDISequence(self, S: str) -> int:
        M = pow(10, 9) + 7
        N = len(S)
        S = '#' + S
        
        dp = [[0] * (N + 1) for _ in range(N + 1)]
        dp[0][0] = 1
        
        for i in range(1, N + 1):
            for j in range(i + 1):
                if S[i] == 'D':
                    for k in range(j, i + 1):
                        dp[i][j] += dp[i-1][k]
                else:
                    # S[i] == 'I'
                    for k in range(0, j):
                        dp[i][j] += dp[i-1][k]
        res = 0
        for i in range(N + 1):
            res += dp[N][i]
        return res % M
        
        


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        MOD = 10**9+7
        
        N = len(S)
        @lru_cache(None)
        
        def dp(i,j):
          if i==0:
            return 1
          elif S[i-1] == 'D':
            return sum(dp(i-1, k) for k in range(j,i)) % MOD
          else:
            return sum(dp(i-1,k) for k in range(j)) % MOD
          
        
        return sum(dp(N,j) for j in range(N+1)) % MOD

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        n=len(s)
        dp=[[0 for i in range(n+1)] for i in range(n+1)]
        dp[0][0]=1
        for i in range(1,n+1):
            for j in range(i+1):
                if(s[i-1]=='D'):
                    for k in range(j,i):
                        dp[i][j]+=dp[i-1][k]
                else:
                    for k in range(j):
                        dp[i][j]+=dp[i-1][k]
        # print(dp)
        return sum(dp[n][:])%(pow(10,9)+7)

class Solution:
    def numPermsDISequence(self, S: str) -> int:
        n = len(S)
        if n <= 1: return 1
        
        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
        dp[0][0] = 1
        
        for idx, s in enumerate(S):
            for end in range(idx+2):
                if s == 'D':
                    for i in range(end, idx+2):
                        dp[idx+1][end] += dp[idx][i]
                else:
                    for i in range(end):
                        dp[idx+1][end] += dp[idx][i]
                        
        # for d in dp: print(d)
        return sum(dp[-1]) % (10 ** 9 + 7)

from functools import lru_cache

class Solution:
    def numPermsDISequence(self, S):
        MOD = 10**9 + 7
        N = len(S)

        @lru_cache(None)
        def dp(i, j):
            # How many ways to place P_i with relative rank j?
            if i == 0:
                return 1
            elif S[i-1] == 'D':
                return sum(dp(i-1, k) for k in range(j, i)) % MOD
            else:
                return sum(dp(i-1, k) for k in range(j)) % MOD

        return sum(dp(N, j) for j in range(N+1)) % MOD

from functools import lru_cache

class Solution:
    def numPermsDISequence(self, S: str) -> int:
        # Dynamic Programming
        # Time  complexity: O(N^3)
        # Space complexity: O(N^2)
        MOD = 10**9 + 7
        N = len(S)

        @lru_cache(None)
        def dp(i, j):
            # How many ways to place P_i with relative rank j?
            if i == 0:
                return 1
            elif S[i - 1] == 'D':
                return sum(dp(i - 1, k) for k in range(j, i)) % MOD
            else:
                return sum(dp(i - 1, k) for k in range(j))

        return sum(dp(N, j) for j in range(N + 1)) % MOD



from functools import lru_cache
class Solution:
    def numPermsDISequence(self, S: str) -> int:
        '''
        这道题目的关键是第一步看到10**9+7知道用dp方法来做
        dp[i]表示范围[0，i]的序列个数，然后发现不好找递推关系
        这个时候肯定是隐藏的信息没用，外面需要通过实际的例子来总结影响个数的另外一个参数
        序列是升还是降跟什么关系最大，那就是最后一个数字。DID模式，我们可以是1032，那么我们再加个D，要求递减
        这个时候多出了一个4来，我们如何改造1032呢，直接加4是不行的，那么加一样的2？改成10432，相当于3，2都+1
        加1呢？改成20431，相当于1，3，2都+1，那么规律是什么。
        如果是D，那么只能放<=最后一个数的数，然后把原来所有>=尾巴的数都+1,最后一个数很重要
        反过来想，如果是I,那么只能放>最后一个数的数，然后原来所有的>=新加的数都+1
        '''
        mod = 10 ** 9 + 7
        n = len(S)
        
        @lru_cache(None)
        def dfs(i, j):  # 位置i处数字j结尾 数字j的范围是0-i
            if i == 0:
                return 1
            elif S[i - 1] == 'D':
                return sum(dfs(i - 1, k) for k in range(j, i)) % mod
            else:
                return sum(dfs(i - 1, k) for k in range(j)) % mod
        return sum(dfs(n, j) for j in range(n + 1)) % mod

from functools import lru_cache
class Solution:
    def numPermsDISequence(self, S: str) -> int:
        MOD = 10**9+7
        N = len(S)
        
        @lru_cache(None)
        def dp(i, j):
            if i==0:
                return 1
            elif S[i-1] == 'D':
                return sum(dp(i-1,k) for k in range(j,i))%MOD
            else:
                return sum(dp(i-1,k) for k in range(j))%MOD
                
                
        return sum(dp(N, j) for j in range(N+1))%MOD

from functools import lru_cache


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        MOD = 10 ** 9 + 7
        
        @lru_cache(None)
        def DP(n, last):
            if n == 0:
                return 1
            if S[n - 1] == 'D':
                return sum(
                    DP(n - 1, x - 1)
                    for x in range(last + 1, n + 1)
                ) % MOD
            else:
                return sum(
                    DP(n - 1, x)
                    for x in range(last)
                ) % MOD

        return sum(
            DP(len(S), i)
            for i in range(len(S) + 1)
        ) % MOD


from functools import lru_cache
class Solution:
    def numPermsDISequence(self, S: str) -> int:
        
        mod = 10**9+7
        
        N = len(S)
        
        @lru_cache(None)
        def dp(i,j):
            print((i,j))
            if i==0:
                return 1
            elif S[i-1]=='D':
                return sum(dp(i-1,k) for k in range(j,i))%mod
            else:
                return sum(dp(i-1,k) for k in range(j))%mod
        
        return sum(dp(N,j) for j in range(N+1))%mod


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        n = len(S)
        mod = 10**9 + 7
        # solns[above][below]
        # if decreasing:
        # answer = sum solns[above+k][below-k-1]
        # if increasing:
        # answer = sum solns[above-k-1][below+k]
        
        solns = [[0] * (n+2) for _ in range(n+2)]
        solns[0][0] = 1
        for i in range(1, n+1):
            for j in range(i+1):
                k = i - j
                if S[-i] == 'D':
                    for r in range(0, k):
                        solns[j][k] += solns[j+r][k-r-1]
                else:
                    for r in range(0, j):
                        solns[j][k] += solns[j-r-1][k+r]
                solns[j][k] %= mod
                
        result = sum(solns[i][n-i] for i in range(n+1))
        return result % mod
                
        


from functools import lru_cache


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        MOD = 10 ** 9 + 7
        
        def presum(n, last):
            return sum(
                DP(n, x)
                for x in range(last)
            )
        
        @lru_cache(None)
        def DP(n, last):
            if n == 0:
                return 1
            if S[n - 1] == 'D':
                return (presum(n - 1, n) - presum(n - 1, last)) % MOD
            else:
                return presum(n - 1, last) % MOD

        return sum(
            DP(len(S), i)
            for i in range(len(S) + 1)
        ) % MOD


class Solution:
    def numPermsDISequence(self, S: str) -> int:
        MOD = 10**9 + 7
        N = len(S)
        
        dp = [[0]*(N+1) for _ in range(N+1)]
        
        def solve(i, j):
            if dp[i][j]:
                return dp[i][j]
            
            if i == 0:
                return 1
            if S[i-1] == 'D':
                dp[i][j] = sum(solve(i-1, k) for k in range(j)) % MOD
            else:
                dp[i][j] = sum(solve(i-1, k) for k in range(j, i)) % MOD  
            
            return dp[i][j]
       
        return sum(solve(N, j) for j in range(N+1)) % MOD