903. Valid Permutations for DI Sequence.cpp
Code\n\nclass Solution {\npublic:\n    int MOD = 1e9+7;\n    long long dp[202][202];\n    long long perms(string &s, int n, int pos, int prev, vector<bool> &vis
**Code**\n```\nclass Solution {\npublic:\n    int MOD = 1e9+7;\n    long long dp[202][202];\n    long long perms(string &s, int n, int pos, int prev, vector<bool> &visited) {\n        if(pos >= n) return 1; \n        if(dp[pos][prev] != -1) return dp[pos][prev];\n        long long ans = 0;\n        for(int i=0;i<=n;i++) {\n            if(!visited[i]) {\n                if(s[pos] == \'D\' && prev > i) {\n                    visited[i] = true;\n                    ans = (ans + perms(s,n,pos+1,i,visited) % MOD) % MOD;\n                    visited[i] = false;\n                }\n                if(s[pos] == \'I\' && prev < i) {\n                    visited[i] = true;\n                    ans = (ans + perms(s,n,pos+1,i,visited) % MOD) % MOD;\n                    visited[i] = false;\n                }\n            }\n        }\n        return dp[pos][prev] = ans;\n    }\n    int numPermsDISequence(string s) {\n        int n = s.length();\n        long long ans = 0;\n        memset(dp,-1,sizeof(dp));\n        for(int i=0;i<=n;i++) {\n            vector<bool> visited(n+1,false);\n            visited[i] = true;\n            ans = (ans + perms(s,n,0,i,visited) % MOD) % MOD;\n        }\n        return ans;\n    }\n};\n```
['C']