C++ Soln || BackTracking + DP
\n#define mod 1000000007;\nclass Solution {\npublic:\n    vector<int> vis;\n    int dp[201][202];\n    int sol(string &s, int ind, int prev){\n        if(ind==s
```\n#define mod 1000000007;\nclass Solution {\npublic:\n    vector<int> vis;\n    int dp[201][202];\n    int sol(string &s, int ind, int prev){\n        if(ind==s.length()+1){return 1;}\n        if(dp[ind][prev+1]!=-1)return dp[ind][prev+1];\n        long ans=0;\n        for(int i=0;i<=s.length();i++){\n            if(vis[i]!=0)continue;\n            if(prev!=-1){\n                if(s[ind-1]==\'D\'){\n                    if(i>prev)break;\n                    vis[i]=1;\n                    ans+=sol(s,ind+1,i);\n                    vis[i]=0;\n                }\n                else{\n                    if(i<prev)continue;\n                    vis[i]=1;\n                    ans+=sol(s, ind+1,i);\n                    vis[i]=0;\n                }\n            }\n            else {\n                vis[i]=1;\n                ans+=sol(s, ind+1, i);\n                vis[i]=0;\n            }\n            \n        }\n        return dp[ind][prev+1]=ans%mod;\n    }\n    int numPermsDISequence(string s) {\n        memset(dp,-1,sizeof dp);\n        vis.resize(s.length()+1,0);\n        return sol(s,0,-1);\n    }\n};\n```
['Dynamic Programming', 'Backtracking', 'C']