[Python3] top-down dp
\n\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        \n        @cache \n        def fn(i, x): \n            """Return number of valid 
\n```\nclass Solution:\n    def numPermsDISequence(self, s: str) -> int:\n        \n        @cache \n        def fn(i, x): \n            """Return number of valid permutation given x numbers smaller than previous one."""\n            if i == len(s): return 1 \n            if s[i] == "D": \n                if x == 0: return 0 # cannot decrease\n                return fn(i, x-1) + fn(i+1, x-1)\n            else: \n                if x == len(s)-i: return 0 # cannot increase \n                return fn(i, x+1) + fn(i+1, x)\n        \n        return sum(fn(0, x) for x in range(len(s)+1)) % 1_000_000_007\n```
['Python3']