c++ 3ms dp top down + prefix sum
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:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\nint mod=1e9+7;\n    int numPermsDISequence(string s) {\n        int n=s.size();\n        vector<vector<int>> dp(n+1,vector<int>(n+1));\n        for(int i=0;i<=n;i++){\n            dp[0][i]=1+i;\n        }\n        for(int i=1;i<=n;i++){\n            for(int j=0;j<=n-i;j++){\n                long long ans=0;\n                if(s[i-1]==\'I\'){\n                    ans=dp[i-1][n+1-i]-dp[i-1][j];\n                    ans=(ans+mod)%mod;\n                }\n                else{\n                    ans+=1LL*dp[i-1][j];\n                    ans=(ans+mod)%mod;\n                }\n                if(j>0) ans+=dp[i][j-1];\n                ans%=mod;\n                dp[i][j]=ans;\n            }\n        }\n        return dp[n][0];\n    }\n};\n```
['C++']