C++ simple and short DFS solution
\n# Code\n\nclass Solution {\n    const int mod = 1e9 + 7;\n    long inverse(long num) {\n        if (num == 1) {\n            return 1;\n        }\n        ret
\n# Code\n```\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) {\n            return 1;\n        }\n        vector<int> left, right;\n        for (int i = 1; i < N; i++) {\n            if (nums[i] < nums[0]) {\n                left.push_back(nums[i]);\n            } else {\n                right.push_back(nums[i]);\n            }\n        }\n\n        int a = left.size();\n        int b = right.size();\n        long res = 1;\n\n        // relative order between left and right\n        // (a+b)! / (b! * a!)\n        for (int i = b+1; i <= a + b; i++) {\n            res = res * i % mod;\n        }\n        for (int i = 1; i <= a; i++) {\n            // res * inverse(i) == res / i\n            res = res * inverse(i) % mod;\n        }\n\n         // order within left: dfs(left)\n         // order within right: dfs(right)\n        return res * dfs(left) % mod * dfs(right) % mod;\n    }\npublic:\n    int numOfWays(vector<int>& nums) {\n        return dfs(nums) - 1;\n    }\n};\n```
['C++']