✅ C++ Solution DP Memoization ✅
\n\n# Code\n\nclass Solution {\npublic:\n    int mod = 1e9+7;\n    int solve(int i,int ind, string &s,vector<int> &visited,vector<vector<int>> &dp){\n        if
\n\n# Code\n```\nclass Solution {\npublic:\n    int mod = 1e9+7;\n    int solve(int i,int ind, string &s,vector<int> &visited,vector<vector<int>> &dp){\n        if(ind==s.size())   return 1;\n\n        if(dp[i][ind]!=-1)  return dp[i][ind];\n\n        long long int ans = 0;\n        if(s[ind]==\'I\'){\n            for(int j=i+1;j<=s.size();j++){\n                if(!visited[j]){\n                    visited[j]=1;\n                    ans = (ans+solve(j,ind+1,s,visited,dp)%mod)%mod;\n                    visited[j]=0;\n                }\n            }\n        }\n        else{\n            for(int j=0;j<i;j++){\n                if(!visited[j]){\n                    visited[j]=1;\n                    ans = (ans+solve(j,ind+1,s,visited,dp)%mod)%mod;\n                    visited[j]=0;\n                }\n            }\n        }\n        return dp[i][ind] = ans%mod;\n    }\n    int numPermsDISequence(string s) {\n        int n=s.size();\n\n        vector<vector<int>> dp(n+1,vector<int>(n+1,-1));\n        vector<int> visited(n+1,0);\n        int ans = 0;\n        for(int i=0;i<=n;i++){\n            visited[i]=1;\n            ans = (ans+solve(i,0, s,visited,dp)%mod)%mod;\n            visited[i]=0;\n        }\n        return ans;\n    }\n};\n```
['String', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']