Python (Simple DP)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def numPermsDISequence(self, s):\n        n, mod = len(s), 10**9+7\n\n        @lru_cache(None)\n        def dfs(i,val):\n            if i == n:\n                return 1\n\n            if s[i] == "D":\n                if val == 0: return 0\n                return dfs(i,val-1) + dfs(i+1,val-1)\n\n            if s[i] == "I":\n                if val == n-i: return 0\n                return dfs(i,val+1) + dfs(i+1,val)\n\n        return sum([dfs(0,j) for j in range(n+1)])%mod\n        \n```
['Python3']