C++ Easy Understanding | | Recursion
\nclass Solution {\n    const int mod = 1e9 + 7;\n    long inverse(long num) {\n        if (num == 1) {\n            return 1;\n        }\n        return mod - 
```\nclass Solution {\n    const int mod = 1e9 + 7;\n    long inverse(long num) {\n        if (num == 1) {\n            return 1;\n        }\n        return mod - mod / num * inverse(mod % num) % mod;\n    }\n\n    int dfs(vector<int>& nums) {\n        int N = nums.size();\n        if (N <= 2)  return 1;\n        \n        vector<int> left, right;\n        for (int i = 1; i < N; i++) \n        {\n            if (nums[i] < nums[0]) \n                left.push_back(nums[i]);\n            else \n                right.push_back(nums[i]);\n         }\n\n        int a = left.size();\n        int b = right.size();\n        long res = 1;\n        for (int i = b+1; i <= a + b; i++) res = res * i % mod;\n        \n        for (int i = 1; i <= a; i++)  res = res * inverse(i) % mod;\n        \n        return res * dfs(left) % mod * dfs(right) % mod;\n    }\n    \npublic:\n    int numOfWays(vector<int>& nums) {\n        return dfs(nums) - 1;\n    }\n};\n```
['Recursion', 'C']