10 lines C++, Time O(n^2), Space O(n), with remark
C++\n// K(s, x) = nums of perms with tail ranking x\n// K(s + \'I\') = K(s, x) + K(s, x+1) + ... + K(s, s.len)\n// K(s + \'D\') = K(s, 0) + K(s, 1) + ... + K(s,
```C++\n// K(s, x) = nums of perms with tail ranking x\n// K(s + \'I\') = K(s, x) + K(s, x+1) + ... + K(s, s.len)\n// K(s + \'D\') = K(s, 0) + K(s, 1) + ... + K(s, x - 1)\n\n// G(s, 0) = 0\n// G(s, x) = K(s, 0) + K(s, 1) + ... + K(s, x - 1)\n\n// K(s + \'I\') = K(s, x) + K(s, x+1) + ... + K(s, s.len) = G(s, s.len + 1) - G(s, x)\n// K(s + \'D\') = K(s, 0) + K(s, 1) + ... + K(s, x - 1) = G(s, x)\n\n// G(s, x + 1) = G(s, x) + K(s, x)\n\n\nclass Solution {\npublic:\n    int numPermsDISequence(string S) {\n        vector<int64_t> G = {0, 1};\n        \n        for (int s_len = 0; s_len < S.size(); ++s_len) {\n            vector<int64_t> nG = {0};\n            \n            for (int x = 0; x <= s_len + 1; ++x) {\n                int64_t k = S[s_len] == \'I\' ? G[s_len + 1] - G[x] : G[x];\n                nG.push_back((nG.back() + k + 1000000007) % 1000000007);\n            }\n            \n            G.swap(nG);\n        }\n        \n        return G[S.size() + 1];\n    }\n};\n```
[]