Java - DP - O(N^3)
\nclass Solution {\n    int MOD = 1000000007;\n    Map<Integer, Integer> cache;\n    public int numPermsDISequence(String s) {\n        cache = new HashMap<>();
```\nclass Solution {\n    int MOD = 1000000007;\n    Map<Integer, Integer> cache;\n    public int numPermsDISequence(String s) {\n        cache = new HashMap<>();\n        return dpRec(s, 0, 0, s.length(), new boolean[s.length()+1]);\n    }\n    private int dpRec(String s, int i, int x, int y, boolean[] vis) {\n        if(i == s.length()){\n            int j;\n            for(j = x; j <= y; j++) if(vis[j] == false) break;\n            return (j <= y) ? 1 : 0;\n        } \n        int key = i*40000 + x*200 + y;\n        if(cache.containsKey(key)) return cache.get(key);\n        int count = 0;\n        for(int j = x; j <= y; j++) {\n            if(vis[j] == false) {\n                vis[j] = true;\n                count += (s.charAt(i) == \'D\') ? dpRec(s, i+1, 0, j-1, vis) : dpRec(s, i+1, j+1, s.length(), vis);\n                count = count%MOD;\n                vis[j] = false;\n            }\n        }\n        cache.put(key, count);\n        return count;\n    }\n}\n```
[]