Python3 divide and conquer solution, slightly quicker than official divide and conquer solution
\nfrom functools import lru_cache\n\n\nclass Solution:\n    def __init__(self):\n        self.mod = 10 ** 9 + 7\n\n    @lru_cache(maxsize=None)\n    def nCk(sel
```\nfrom functools import lru_cache\n\n\nclass Solution:\n    def __init__(self):\n        self.mod = 10 ** 9 + 7\n\n    @lru_cache(maxsize=None)\n    def nCk(self, n, k):\n        if k == 1: return n\n        if k == 0 or n == k: return 1\n        return self.nCk(n - 1, k - 1) + self.nCk(n - 1, k)\n\n    @lru_cache(maxsize=None)\n    def numPermsDISequence(self, s: str) -> int:\n        if len(s) <= 1: return 1\n        n = len(s) + 1\n        ans = 0\n\t\t#Insert max number in every \'DI\' part, left and right part are choosed from left numbers\n        for i in range(n - 1):\n            if s[i:i + 2] == \'ID\': ans += self.nCk(n - 1, i + 1) * self.numPermsDISequence(s[:i]) * self.numPermsDISequence(s[i + 2:])\n\t\t#Insert max number at start position if s[0] == \'D\'\n        if s[0] == \'D\': ans += self.numPermsDISequence(s[1: n - 1])\n\t\t#Same insert max number at end\n        if s[n - 2] == \'I\': ans += self.numPermsDISequence(s[: n - 2])\n        return ans % self.mod\n```
['Divide and Conquer', 'Python3']