Detailed comments for an O(N^2) solution
\n# Code\n\nclass Solution {\npublic:\n\n    int numPermsDISequence(string s) {\n        int N = s.size() + 1;\n        vector<vector<int>> dp(N, vector<int>(N)
\n# Code\n```\nclass Solution {\npublic:\n\n    int numPermsDISequence(string s) {\n        int N = s.size() + 1;\n        vector<vector<int>> dp(N, vector<int>(N));\n        const int mod = 1e9 + 7;\n\n        // dp[i][j] : answers for length=i+1 (using number [0,1,..,i]) that ends with j (j <= i)\n        for (int j = 0; j < N; j++) {\n            dp[0][j] = 1;\n        }\n\n        for (int i = 1; i < N; i++) {\n            for (int j = 0; j <= i; j++) {\n                // when we append j to the array, in order to avoid duplicate, by default, all the elements >= j in the previous array will automatically increment by one\n                // e.g. [2, 1, 0] + [1] => [3, 2, 0, 1]\n\n                if (s[i-1] == \'I\') {\n                    // dp[i][j] = dp[i-1][0] + dp[i-1][1] + .. dp[i-1][j-1]\n                    dp[i][j] = j ? dp[i-1][j-1] : 0;\n                } else {\n                    // dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + .. dp[i-1][i-1]\n                    dp[i][j] = dp[i-1][i-1] - (j ? dp[i-1][j-1] : 0);\n                }\n            }\n\n            // change dp[i][j] to prefix sum so that we can have O(N^2) overall complexity instead of O(N^3)\n            for (int j = 1; j <= i; j++) {\n                dp[i][j] += dp[i][j-1];\n                dp[i][j] %= mod;\n                if (dp[i][j] < 0) {\n                    dp[i][j] += mod;\n                }\n            }\n        }\n\n        return dp[N-1][N-1];\n    }\n};\n```
['C++']