Python3 Top Down DP
\nfrom functools import lru_cache\nclass Solution:\n    def numPermsDISequence(self, S: str) -> int:\n        n = len(S) + 1\n        @lru_cache(maxsize = 40000
```\nfrom functools import lru_cache\nclass Solution:\n    def numPermsDISequence(self, S: str) -> int:\n        n = len(S) + 1\n        @lru_cache(maxsize = 40000)\n        def dfs(lastPos, pos):\n            total = 0\n            if pos == 0:\n                for i in range(n):\n                    total += dfs(i, pos + 1)\n                return total%1000000007\n            letter = S[pos - 1]\n            if pos == len(S):\n                if letter == \'I\':\n                    return 1 - lastPos\n                else:\n                    return lastPos\n            else:\n                if letter == \'I\':\n                    for i in range(lastPos, n-pos):\n                        total += dfs(i, pos + 1)\n                else:\n                    for i in range(lastPos):\n                        total += dfs(i, pos + 1)\n                        \n                return total%1000000007\n            \n        return dfs(0,0)%1000000007\n```
[]