C++ Explanation
Took me quite a while to get it, but the \nnumber of ways to arrange nums = ways to arrange the numbers in the left subtree * ways to arrange numbers in right s
Took me quite a while to get it, but the \nnumber of ways to arrange nums = ways to arrange the numbers in the left subtree * ways to arrange numbers in right subtree * positions to fit the left/right subtree back into the original array\n\n```\nclass Solution {\npublic:\n    int mod=1e9+7;\n    long long power(long long a, long long b) {\n        long long res=1;\n        while (b>0) {\n            if (b&1) res*=a, res%=mod;\n            b/=2;\n            a*=a;\n            a%=mod;\n        }\n        return res;\n    }\n    long long choose(long long a, long long b) {\n        long long res=1;\n        for (long long i=1; i<=b; i++) {\n            res*=(a-i+1);\n            res%=mod;\n            res*=power(i, mod-2);\n            res%=mod;\n        }\n        return res;\n    }\n    long long solve(vector<int> nums) {\n        if (nums.size()<=2) return 1;\n        vector<int> left, right;\n        for (int i=1; i<nums.size(); i++) {\n            if (nums[i]<nums[0]) left.push_back(nums[i]);\n            else right.push_back(nums[i]);\n        }\n        return ((choose(nums.size()-1, right.size())*solve(right)%mod)*solve(left))%mod;\n    }\n    int numOfWays(vector<int> &nums) {\n        return solve(nums)-1;\n    }\n};\n```
[]