MEMOIZATION DP
\nclass Solution {\npublic:\n    int dp[203][203];\n    int mod=1e9+7;\n    int solve(int index , string& s, vector<int> & visited , int prev){\n        if(inde
```\nclass Solution {\npublic:\n    int dp[203][203];\n    int mod=1e9+7;\n    int solve(int index , string& s, vector<int> & visited , int prev){\n        if(index==s.size()) return 1;\n        if(dp[index][prev]!=-1) return dp[index][prev];\n        int n=s.size();\n        long long temp=0;\n        if(s[index]==\'D\'){\n            //0 to prev-1\n            for(int i=0;i<=prev-1;i++){\n                if(visited[i]==0){\n                    visited[i]=1;\n                    temp=(temp%mod+(long long)solve(index+1,s,visited,i)%mod)%mod;\n\n                    visited[i]=0;\n                }\n            }\n        }else {\n            //prev+1 to n\n            for(int i=prev+1;i<=n;i++){\n                if(visited[i]==0){\n                    visited[i]=1;\n                    temp=(temp%mod+(long long)solve(index+1,s,visited,i)%mod)%mod;\n                    visited[i]=0;\n                }\n            }\n        }\n        return dp[index][prev]=temp;\n    }\n    int numPermsDISequence(string s) {\n        memset(dp,-1,sizeof dp);\n        int n=s.size();\n        vector<int> visited(n+1,0);\n        int count=0;\n        for(int i=0;i<=n;i++){\n            visited[i]=1;\n            count= (count%mod+(long long)solve(0,s,visited,i)%mod)%mod;\n            visited[i]=0;\n        }\n        return count;\n    }\n};\n```
[]