Easy and simple solution with explanation
If you not understand problem clearly then here is explanation\nLet\'s suppose we have given array [3,4,5,1,2] and empty tree\nthen we have to place element in 
**If you not understand problem clearly then here is explanation**\nLet\'s suppose we have given *array* [3,4,5,1,2] and empty tree\nthen we have to place element in tree by order they comes i.e.\nwe get first element 3 make it root then we have element 4 make it to right child of 3,now element 5 come make it to right child of 4 then element 1 come make it to left child of 3 which is its correct position according to BST rule (i.e. smaller element left side and larger element right side) now 2 come make it to right child of 1.\nNow we have to find how many arrangements of give permutation give same BST.```\n\ni.e. 3 as root, 4 is right child of 3,5 is right child of 4, 1 is left child of 3 and 2 is right child of 1.\nHint: writes all arrangement of array try to find pattern in this.\n(Sorry for poor English).\n\n```\nint mode=1e9+7;\nclass Solution {\npublic:\n    vector<vector<long long>> bio;\n    long long dfs(vector<int> &nums){\n        if(nums.size()<3){\n            return 1;\n        }\n        vector<int> left,right;\n        int n=nums.size();\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        int k=left.size();\n        return bio[n][k]*dfs(left)%mode *dfs(right)%mode;\n    }\n    int numOfWays(vector<int>& nums) {\n        int n=nums.size();\n        bio.resize(0);\n        bio.resize(n+4);\n        bio[1]={1};\n        bio[2]={1,1};\n        for(int i=3;i<=n;i++){\n            bio[i].resize(i,1);\n            for(int j=1;j<i-1;j++){\n                bio[i][j]=(bio[i-1][j-1]+bio[i-1][j])%mode;\n            }\n        }\n        return (dfs(nums)-1)%mode;\n    }\n};\n```
['C++']