[C++] Beginner Friendly, DP Solution
\nclass Solution {\npublic:\n    int mod=1000000007;\n    int solve(string &s, int index, vector<bool> &vis, int last, vector<vector<int> > &dp){\n        //if 
```\nclass Solution {\npublic:\n    int mod=1000000007;\n    int solve(string &s, int index, vector<bool> &vis, int last, vector<vector<int> > &dp){\n        //if we reach the last index, there will be single element left we can do this in one way.\n        if(index == s.size()){\n            return 1;\n        }\n        \n        if(dp[index][last] != -1) return dp[index][last];\n        \n        //when we need less than last one\n        long long cnt = 0;\n        if(s[index] == \'D\'){\n            for(int i=0; i<last; i++){\n                if(vis[i]) continue;\n                vis[i] = true;\n                cnt+=(solve(s, index+1, vis, i, dp))%mod;\n                vis[i] = false;\n            }\n        }\n        \n        //when we need greater than last one\n        else{\n            for(int i=last+1; i<=s.size(); i++){\n                if(vis[i]) continue;\n                vis[i] = true;\n                cnt+=(solve(s, index+1, vis, i, dp))%mod;\n                vis[i] = false;\n            }\n        }\n        \n        return dp[index][last] = cnt%mod;\n    }\n    int numPermsDISequence(string s) {\n        vector<bool> vis(s.size()+1, false);\n        vector<vector<int> > dp(s.size()+2, vector<int>(s.size()+2, -1));\n        \n        //start with any number at first position, then apply conditions in function\n        long long cnt = 0;\n        for(int i=0; i<=s.size(); i++){\n            vis[i] = true;\n            cnt+=(solve(s, 0, vis, i, dp))%mod;\n            vis[i] = false;\n        }\n        \n        return cnt%mod;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C']