EASY DP || C++ || 👍✅
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:O(N^3)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    #define ll long long\n    const int mod = 1e9+7;\n    int solve(int ind, int prev, string s, int n,vector<int>&vis,vector<vector<int>>&dp){\n        if(ind>=n)return 1;\n        if(dp[ind][prev]!=-1)return dp[ind][prev];\n\n        ll ans=0;\n        for(int i=0;i<=n;i++){\n            if(i!=prev && vis[i]==0){\n                if(s[ind]==\'D\' && i<prev){\n                    vis[i]=1;\n                    ans=(ans+solve(ind+1,i,s,n,vis,dp))%mod;\n                    vis[i]=0;\n                }\n                if(s[ind]==\'I\' && i>prev){\n                    vis[i]=1;\n                    ans= (ans+solve(ind+1,i,s,n,vis,dp))%mod;\n                    vis[i]=0;\n                }\n            }\n        }\n        return dp[ind][prev]=ans%mod;\n    }\n    int numPermsDISequence(string s) {\n        \n        int n = s.length();\n        ll ans=0;\n        vector<vector<int>>dp(n+1,vector<int>(n+1,-1));\n        for(int i=0;i<=n;i++){\n            vector<int>vis(n+2,0);\n            vis[i]=1;\n            \n            ans= (ans+solve(0,i,s,n,vis, dp))%mod;\n        }\n        return ans;\n\n    }\n};\n```
['C++']