C++ Easy
class Solution {\npublic:\n    int mod = 1e9 + 7;\n    // unordered_setst;\n    int perm(int i, int prev, int n, string &s, vector>&dp, vector&vis)\n    {\n    
class Solution {\npublic:\n    int mod = 1e9 + 7;\n    // unordered_set<int>st;\n    int perm(int i, int prev, int n, string &s, vector<vector<int>>&dp, vector<bool>&vis)\n    {\n        //cout<<"HERE"<<i<<"\\n";\n        if(i<0)\n        {\n            return 1;\n        }\n        if(dp[i][prev] != -1)\n        {\n            return dp[i][prev];\n        }\n        \n        int ways = 0;\n        \n        if(i == n)\n        {\n            for(int j=0; j<=n;j++)\n            {\n                int x = j;\n                vis[x] = true;\n                //cout<<x<<"\\n";\n                ways = (ways + perm(i-1, x, n, s, dp, vis))%mod;\n                //cout<<ways<<" "<<x<<"\\n";\n                vis[x] = false;\n            }\n        }\n        else\n        {\n            if(s[i] == \'D\')\n            {\n                for(int j=0; j<=n; j++)\n                {\n                    if(vis[j] == true) continue;\n                    int x = j;\n                    if(prev < x)\n                    {\n                        vis[x] = true;\n                        ways = (ways + perm(i-1, x,n, s, dp, vis))%mod;\n                        vis[x] = false;\n                    }\n                    \n                }\n            }\n            else\n            {\n                for(int j=0; j<=n; j++)\n                {\n                    if(vis[j] == true) continue;\n                    int x = j;\n                    if(prev > x)\n                    {\n                        vis[x] = true;\n                        ways = (ways + perm(i-1, x,n, s, dp, vis))%mod;\n                        vis[x] = false;\n                    }\n                }\n            }\n        }\n        return dp[i][prev] = ways;\n    }\n    \n    \n    int numPermsDISequence(string s) {\n        vector<bool>vis(s.size()+10, -1);\n        for(int i=0; i<= s.size();i++)\n        {\n            vis[i] = false;\n            //cout<<i<<"\\n";\n        }\n        vector<vector<int>>dp(s.size()+10, vector<int>(s.size()+10, -1));\n        return perm(s.size(), s.size()+5, s.size(), s, dp, vis);\n        return 0;\n    }\n};
['Dynamic Programming', 'C']