[C++] algebra, module-inverse, comb(N, K)
\nclass Solution {\n    const int64_t MOD = 1000000007;\n    \n    int64_t comb(int N, int K) {\n        int64_t nx = 1;\n        // i!\n        for (int64_t i 
```\nclass Solution {\n    const int64_t MOD = 1000000007;\n    \n    int64_t comb(int N, int K) {\n        int64_t nx = 1;\n        // i!\n        for (int64_t i = 2; i <= N; ++i) nx = nx * i % MOD;\n\n        const int M = max(K, N - K) + 1;\n        vector<int64_t> inv(M, 0), inv_kx(M, 0);\n        inv[0] = inv_kx[0] = inv[1] = inv_kx[1] = 1;\n        // https://cp-algorithms.com/algebra/module-inverse.html\n        // 1 / i!\n        for (int64_t i = 2; i < M; ++i) {\n            inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;\n            inv_kx[i] = inv_kx[i - 1] * inv[i] % MOD;\n            // cout << i << ":" << inv_kx[i] << "  ";\n        }\n        \n        // N! / (K! * (N - K)!)\n        return nx * inv_kx[K] % MOD * inv_kx[N - K] % MOD;\n    }\n    \n    int64_t ways(vector<int>& nums) {\n        if (nums.size() <= 2) return 1;\n        \n        vector<int> l, r;\n        for (int i = 1; i < nums.size(); ++i)\n            nums[i] < nums[0] ? l.push_back(nums[i]) : r.push_back(nums[i]);\n        int64_t c = comb(l.size() + r.size(), l.size()), lw = ways(l), rw = ways(r);\n        return c * lw % MOD * rw % MOD;\n    }\n    \npublic:\n    int numOfWays(vector<int>& nums) {\n        // root = nums[0]\n        // l[i] < root; r[i] > root\n        // comb(l.size + r.size, l.size) * numOfWays(l) * numOfWays(r) - 1\n        \n        return ways(nums) - 1; \n    }\n};\n```
[]