[C++]--Just using recursion, very Clean and  Easy to understand--O(n^2)
So, we can know that for a fixed root, the left subtree elements and the right subtree elements are also fixed.\n\nWe can find the left subtree elements which a
So, we can know that for a fixed root, the left subtree elements and the right subtree elements are also fixed.\n\nWe can find the ``left subtree elements`` which are all the elements that is **smaller** than root value, and ``right subtree elements`` which are **greater** than root value.\n\nAnd in order to make it identical with original BST, we should **keep the relative order** in left subtree elements and in right subtree elements.\n\nAssume the lenght of left subtree elements is ``left_len`` and right is ``right_len``, they **can change their absolute position** but **need to keep their relative position** in either left subtree or right right subtree. \n\nSo as the subtree, so we use recursion.\n\n**Example**\n```\n[3, 4, 5, 1, 2] // original array with root value is 3\n\n[1, 2] // left sub-sequence, left_len = 2\n[4, 5] // right sub-sequence, right_len = 2\n\n// the left sub-sequence and right sub-sequence take 4 position, because left_len + right_len = 4\n\n// keep relative order  in left sub-sequence and in right-sequence, but can change absolute position.\n[1, 2, 4, 5]\n[1, 4, 2, 5]\n[1, 4, 5, 2]\n[4, 1, 2, 5]\n[4, 1, 5, 2]\n[4, 5, 1, 2]\n// number of permutation: 6\n\n// in code, we use Pascal triangle to keep a table of permutations, so we can look up the table and get permutation result in O(1)\n```\n\n**Code**\n```\nclass Solution {\npublic:\n    int numOfWays(vector<int>& nums) {\n        long long mod = 1e9 + 7;\n\t\tint n = nums.size();\n        \n\t\t// Pascal triangle\n        table.resize(n + 1);\n        for(int i = 0; i < n + 1; ++i){\n            table[i] = vector<long long>(i + 1, 1);\n            for(int j = 1; j < i; ++j){\n                table[i][j] = (table[i-1][j-1] + table[i-1][j]) % mod;\n            }\n        }\n        \n        long long ans = dfs(nums, mod);\n        return ans % mod - 1;\n    }\n    \nprivate:\n    vector<vector<long long>> table;\n    long long dfs(vector<int> &nums, long long mod){\n        int n = nums.size();\n        if(n <= 2) return 1;\n        \n\t\t// find left sub-sequence elements and right sub-sequence elements\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\t\t\n\t\t// recursion with left subtree and right subtree\n        long long left_res = dfs(left, mod) % mod;\n        long long right_res = dfs(right, mod) % mod;\n\t\t\n\t\t// look up table and multiple them together\n\t\tint left_len = left.size(), right_len = right.size();\n        return (((table[n - 1][left_len] * left_res) % mod) * right_res) % mod;\n    }\n};\n```
[]