The constraint is sort of too loose for backtracking to pass
Code\n\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        N = len(s)+1\n        seen = set([])\n        @cache\n        def dp(i,prev):
# Code\n```\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        N = len(s)+1\n        seen = set([])\n        @cache\n        def dp(i,prev):\n            if i == N-1:\n                return 1\n            res = 0\n            if prev == -1:\n                for k in range(N):\n                    seen.add(k)\n                    res += dp(i,k) % (10**9+7)\n                    seen.remove(k)\n            elif s[i] == \'I\':\n                for k in range(prev+1,N):\n                    if k not in seen:\n                        seen.add(k)\n                        res += dp(i+1,k) % (10**9+7) \n                        seen.remove(k)\n            else:\n                for k in range(prev):\n                    if k not in seen:\n                        seen.add(k)\n                        res += dp(i+1,k) % (10**9+7)\n                        seen.remove(k)\n            return res % (10**9+7)\n            \n\n            \n        return dp(0,-1) % (10**9+7)\n\n\n            \n\n        \n```
['Backtracking', 'Python3']