DP - All possible permutations
Code
# Code
```cpp []
const int MOD = 1e9 + 7;
class Solution {
public:
    int getAns(int i, int n, char ch, int num, string& s, vector<int>& count,
               vector<vector<int>>& dp) {
        if (i == n) {
            for (int j = 0; j <= n; j++)
                if (count[j] == 1) {
                    if (ch == 'D' && num > j)
                        return 1;
                    if (ch == 'I' && num < j)
                        return 1;
                    return 0;
                }
        }
        if (dp[i][num] != -1)
            return dp[i][num];

        int ans = 0;
        if (ch == 'D') {
            for (int j = 0; j <= num - 1; j++) {
                if (count[j] > 0) {
                    count[j]--;
                    ans = (ans + getAns(i + 1, n, s[i], j, s, count, dp)) % MOD;
                    count[j]++;
                }
            }
        } else {
            for (int j = num + 1; j <= n; j++) {
                if (count[j] > 0) {
                    count[j]--;
                    ans = (ans + getAns(i + 1, n, s[i], j, s, count, dp)) % MOD;
                    count[j]++;
                }
            }
        }
        return dp[i][num] = ans;
    }

    int numPermsDISequence(string s) {
        int n = s.size();
        vector<int> count(n + 1, 1);
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
        char ch = s[0];
        int ans = 0;
        for (int i = 0; i <= n; i++) {
            count[i]--;
            ans = (ans + getAns(1, n, s[0], i, s, count, dp)) % MOD;
            count[i]++;
        }
        return ans;
    }
};
```
['C++']