✅100% Fast | C++ | Easy to understand  & clean approach| TC: O(N) 🔥| BST & Factorial Precomputation
Intuition\nPrecomputation of factorial of a number till 1000 is required.\nDeclare a global variable to keep the final answer(say ans).\n \nStep1: Create a bina
# Intuition\nPrecomputation of factorial of a number till 1000 is required.\nDeclare a global variable to keep the final answer(say ans).\n \nStep1: Create a binary search tree.\nStep2: For every node, find the no of nodes in left subtree(say L) and no of nodes in right subtree(say R) then do **ans  = ans* (L+R combination L);** //calculating the total number of permutations possible\nStep3: return ans-1 as the final result.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nPrecomputation of factorial of a number till 1000 is required.\nDeclare a global variable to keep the final answer(say ans).\n \nStep1: Create a binary search tree.\nStep2: For every node, find the no of nodes in left subtree(say L) and no of nodes in right subtree(say R) then do **ans  = ans* (L+R combination L);** //calculating the total number of permutations possible\nStep3: return ans-1 as the final result.\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N\\*h) to create a BST, where h is the maximum height of a tree\n# Code\n```\n\nclass Solution {\npublic:\n    #define ll long long\n    ll mod = 1e9+7;\n    struct Node{\n        int value;\n        Node* left;\n        Node* right;\n        Node(int val){\n            value = val;\n            left = NULL;\n            right = NULL;\n        }\n    };\n\n    ll fact[1001];\n    void precalc() {\n        fact[0] = 1;\n        for(ll i = 1; i < 1001; i++)\n            fact[i] =(fact[i - 1]*i)%mod;\n            // fact[i]=fact[i-1]*i;\n    }\n\n    ll inv(ll x) {\n        return x <= 1 ? x : mod - (long long)(mod/x) * inv(mod % x) % mod;\n    }\n    \n    ll mul(ll x, ll y) {\n        return ((x%mod) * 1ll * (y%mod)) % mod;\n    }\n\n    ll divide(ll x, ll y) {\n        return mul(x, inv(y));\n    }\n\n    void insertBST(Node* root,int val){\n        if(root->value>val){\n            if(root->left==NULL){\n                root->left = new Node(val);\n            }\n            else{\n                insertBST(root->left,val);\n            }\n        }\n        else if(root->value<val){\n            if(root->right==NULL){\n                root->right = new Node(val);\n            }\n            else{\n                insertBST(root->right,val);\n            }\n        }\n    }\n    \n    void printBST(Node* root){\n        if(root==NULL) return;\n        printBST(root->left);\n        cout<<root->value<<" ";\n        printBST(root->right);\n    }\n\n    \n    ll compute(ll left,ll right){\n        if(left==0 or right == 0) return 1LL;\n        return divide(fact[left+right],mul(fact[left],fact[right]));\n    }\n\n    ll ans = 1;\n    ll calculatePermutations(Node* root){\n        if(root==NULL){\n            return 0;\n        }\n\n        ll left = calculatePermutations(root->left);\n        ll right = calculatePermutations(root->right);\n        ll pnc = compute(left,right)%mod;\n        ans = mul(ans,pnc);\n        return 1+left+right;\n    }\n    int numOfWays(vector<int>& nums) {\n        Node* root = new Node(nums[0]);\n        //create BST\n        for(int i = 0;i<nums.size();i++){\n            insertBST(root,nums[i]);\n        }\n\n        precalc(); //precalculating the factorial till 1000\n        calculatePermutations(root);\n        return ans - 1;\n    }\n};\n```
['C++']