Easiest Solution
\n\n# Code\njava []\nclass Solution {\n    public int numPermsDISequence(String s) {\n\tint n = s.length();\n\tint[][] dp = new int [n+2][2];\n\tint mod = 10000
\n\n# Code\n```java []\nclass Solution {\n    public int numPermsDISequence(String s) {\n\tint n = s.length();\n\tint[][] dp = new int [n+2][2];\n\tint mod = 1000000007;\n\tdp[1][0] = 1;\n\tfor(int i = 1; i<=n; i++){\n\t\tif(s.charAt(i-1)==\'I\') {\n\t\t\tfor(int j = 0; j<=i; j++) dp[j+1][i&1]=(dp[j][(i+1)&1] + dp[j][i&1])%mod;  \n\t\t} else {\n\t\t\tfor(int j = 0; j<=i; j++) dp[j+1][i&1]=((dp[i][(i+1)&1] + mod - dp[j][(i+1)&1])%mod + dp[j][i&1])%mod;\n\t\t} \n\t}\n\treturn dp[n+1][n&1];\n}\n}\n```\n```c++ []\nclass Solution {\npublic:\n    int visited[201];\n    int mod = 1e9+7;\n    map<pair<int,int>,int>mp;\n    int solve(int idx , int last,string &s){\n        //base case\n        if(idx<0)return 1;\n        \n        if(mp.count({idx,last}))\n            return mp[{idx,last}];\n        int ans = 0 ;\n        \n        //hash means any number can be insertd at last position\n        if(s[idx]==\'#\'){\n            for(int i=0;i<s.size();i++){\n                if(!visited[i]){\n                    visited[i]=1;\n                    ans = (ans + solve(idx-1,i,s))%mod;\n                    visited[i]=0;\n                }\n            }\n        }\n        \n        if(s[idx]==\'D\'){\n            for(int i=last+1;i<s.size();i++){\n                if(!visited[i]){\n                    visited[i]=1;\n                    ans = (ans + solve(idx-1,i,s))%mod;\n                    visited[i]=0;\n                }\n            }            \n        }\n        \n        if(s[idx]==\'I\'){\n            for(int i=0;i<last;i++){\n                if(!visited[i]){\n                    visited[i]=1;\n                    ans = (ans + solve(idx-1,i,s))%mod;\n                    visited[i]=0;\n                }\n            }             \n        }\n        \n        return mp[{idx,last}] = ans;\n        \n    }\n    int numPermsDISequence(string s) {\n        s.push_back(\'#\');\n        int n=s.size();\n        return solve(n-1,0,s);\n    }\n};\n```
['C++', 'Java']