EXPLAINED | Beginer friendly | Recursion | C++ | 90% FAST | O(n^2)
Intuition\n Describe your first thoughts on how to solve this problem. \n\nIf you are not familiar with how to form a BST form the array, you should definitely 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nIf you are not familiar with how to form a BST form the array, you should definitely check it out online. [resource link](https://devcamp.com/trails/development-soft-skills/campsites/understanding-algorithms/guides/how-to-create-binary-search-tree-array)  - idk if this is the best, but this looks good enough to establish a basic understanding.\n\nNext, we have to observe that arrays which satisfy topological ordering of the input array will produce the same tree. In other words, for the tree produced, there can be multiple valid topological sorts. All there arrays will still produce the same tree.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n\nI have implemented the idea given in [this](https://codeforces.com/blog/entry/75627) blog post in code forces. It basically tells us that for a tree, the first element of the topological sort is gonna be the node itself. Next, we need to look at the topological sort of the left and right subtrees ( you can see the recursion forming now... ). When creating the rest of the topological sort for the currennt node, we need to preserve the ordering among the elements of these two lists.\n\nLet us say the n1, n2 are the length of the topological sorts of each subtree (which is also the number of nodes in the subtree), and t1, t2 be the number of topological sorts possible for each subtree. \n\nThe remaining part of the topo-sort should be n1+n2 long. First we select n1 positions from n1+n2 positions, which is (n1+n2)C(n1) number of ways. Now these n1 positions can be filled in t1 ways, and the remaining n2 positinos in t2 ways, resulting in the number of topo sorts for current node to be **(n1+n2)C(n1) * t1 * t2**. The number of nodes in the subtree naturally is **n1+n2+1**\n\n# Complexity\n- Time complexity: O(n^2) - Creating BST\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(n) - facts array to store factorials\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nPlease upvote the solutions if you find it helpful :)\n# Code\n```\nclass Solution {\n    struct BSTNode{\n        int val;\n        BSTNode *left, *right;\n    \n        BSTNode( int x ) {\n            val = x;\n            left = NULL, right = NULL;\n        }\n    };\n\n    void insert_into_BST( int val, BSTNode* root ) {\n        BSTNode* prev = NULL;\n\n        while( root ) {\n            prev = root;\n            if( val > root->val ) root = root->right;\n            else root = root->left;\n        }\n\n        if( val > prev->val ) prev->right = new BSTNode( val );\n        else prev->left = new BSTNode( val );\n    }\n\n    const int mod = 1e9+7;\n    vector<long long> facts;\n\n    pair<int,long long> solve( BSTNode* curr ) {\n        if( curr==NULL ) return {0,1};\n\n        auto [n1, t1] = solve( curr->left );\n        auto [n2, t2] = solve( curr->right );\n\n        t1 = (t1*t2) % mod;\n        return { n1+n2+1, (t1*comb(n1+n2, n1))%mod };\n    }\n\n    int comb( int n, int r ) {\n        long long num = facts[n],\n            denom = ( facts[n-r] * facts[r] ) % mod;\n\n        // when p is prime, a^-1 mod p = a^p-2 mod p\n        long long inv = fast_exponent( denom, mod-2 );\n\n        return (num*inv)%mod;\n    }\n\n    long long fast_exponent( long long base, int exp ) {\n        if( exp==0 ) return 1;\n        if( exp%2==0 ) {\n            long long t = fast_exponent( base, exp/2 );\n            return (t*t)%mod;\n        }\n        return (fast_exponent(base, exp-1 )*base) % mod;\n    }   \npublic:\n    int numOfWays(vector<int>& nums) {\n        int n = nums.size();\n        BSTNode* root = new BSTNode( nums[0] );\n\n        facts.resize(n+1);\n        facts[0]=1;\n        for( int i=1; i<=n; i++ ) facts[i] = (i*facts[i-1])%mod;\n\n        for( int i=1; i<n; i++ ) insert_into_BST( nums[i], root );\n\n        return solve( root ).second-1;\n    }\n};\n```
['C++']