C++ Easy
c++\nclass Solution {\npublic:\n    int n;\n    string s;\n    int mod = 1e9 + 7;\n    map<pair<int,int>,int>dp;\n    int countways(int id,int prev,vector<bool>
```c++\nclass Solution {\npublic:\n    int n;\n    string s;\n    int mod = 1e9 + 7;\n    map<pair<int,int>,int>dp;\n    int countways(int id,int prev,vector<bool>&taken){\n\n        if(id==n+1){\n            return 1;\n        }\n        if(dp.find({id,prev})!=dp.end()) return dp[{id,prev}];\n        int ans = 0;\n        if(s[id-1]==\'D\'){\n            for(int i = 0;i<=prev;i++){\n                if(taken[i]==true) continue;\n                taken[i] = true;\n                ans+=countways(id+1,i,taken)%mod;\n                ans%=mod;\n                taken[i] = false;\n            }\n        }\n        else{\n            for(int i = prev+1;i<=n;i++){\n                if(taken[i]==true) continue;\n                taken[i] = true;\n                ans+=countways(id+1,i,taken)%mod;\n                ans%=mod;\n                taken[i] = false;\n            }\n        }\n        return dp[{id,prev}] = ans%mod;\n    }\n    int numPermsDISequence(string _s) {\n        s = _s;\n        n = s.size();\n        vector<bool>taken(n+1,false);\n        int ans = 0;\n        for(int i = 0;i<=n;i++){\n            taken[i] = true;\n            ans+=countways(1,i,taken)%mod;\n            ans%=mod;\n            taken[i] = false;\n        }\n        return ans;\n    }\n};\n```
[]