C++ dfs dp memo
```cpp []
class Solution {
public:
    vector<vector<int>> dp;
    const int m = 1e9 + 7;
    string s;
    
    int numPermsDISequence(string str) {
        s = str;
        int n = s.size();
        dp.resize(n, vector<int>(n + 1, -1));
        int ans = 0;
        for (int i = 0; i <= n; ++i){
            ans = (ans + dfs(0, i)) % m;
        }
        return ans;
    }

    int dfs(int i, int a){
        if (i == s.size()) return 1;
        if (dp[i][a] == -1) {
            int b = s.size() - i - a;
            long long ways = 0;
            if (s[i] == 'I') {
                for (int k = 1; k <= a; ++k) {
                    ways = (ways + dfs(i + 1, a - k)) % m;
                }
            } else {
                for (int k = 1; k <= b; ++k) {
                    ways = (ways + dfs(i + 1, a + b - k)) % m;
                }
            }
            dp[i][a] = ways;
        }
        return dp[i][a];
    }
};
```
['C++']