Solution
C++ []\nclass Solution {\npublic:\n        int numPermsDISequence(string S) {\n        int n = S.length(), mod = 1e9 + 7;\n        vector<vector<int>> dp(n + 1,
```C++ []\nclass Solution {\npublic:\n        int numPermsDISequence(string S) {\n        int n = S.length(), mod = 1e9 + 7;\n        vector<vector<int>> dp(n + 1, vector<int>(n + 1));\n        for (int j = 0; j <= n; j++) dp[0][j] = 1;\n        for (int i = 0; i < n; i++)\n            if (S[i] == \'I\')\n                for (int j = 0, cur = 0; j < n - i; j++)\n                    dp[i + 1][j] = cur = (cur + dp[i][j]) % mod;\n            else\n                for (int j = n - i - 1, cur = 0; j >= 0; j--)\n                    dp[i + 1][j] = cur = (cur + dp[i][j + 1]) % mod;\n        return dp[n][0];\n    }\n};\n```\n\n```Python3 []\nfrom itertools import accumulate\n\nclass Solution:\n    def numPermsDISequence(self, S):\n        dp = [1] * (len(S) + 1)\n        for a, b in zip("I" + S, S):\n            dp = list(accumulate(dp[:-1] if a == b else dp[-1:0:-1]))\n        return dp[0] % (10**9 + 7)\n```\n\n```Java []\nclass Solution {\n\tpublic int numPermsDISequence(String s) {\n\t\tint length = s.length();\n\t\tint mod = 1000000007;\n\t\tint[] dp1 = new int[length + 1];\n\t\tint[] dp2 = new int[length];\n\t\tfor (int j = 0; j <= length; j++) {\n\t\t\tdp1[j] = 1;\n\t\t}\n\t\tfor (int i = 0; i < length; i++) {\n\t\t\tif (s.charAt(i) == \'I\') {\n\t\t\t\tfor (int j = 0, curr = 0; j < length - i; j++) {\n\t\t\t\t\tdp2[j] = curr = (curr + dp1[j]) % mod;\n\t\t\t\t}\n\t\t\t} else {\n\t\t\t\tfor (int j = length - i - 1, curr = 0; j >= 0; j--) {\n\t\t\t\t\tdp2[j] = curr = (curr + dp1[j + 1]) % mod;\n\t\t\t\t}\n\t\t\t}\n\t\t\tdp1 = Arrays.copyOf(dp2, length);\n\t\t}\n\t\treturn dp1[0];\n\t}\n}\n```\n
['C++', 'Java', 'Python3']