O(N) simple&fast
First, the answer can be expressed as n!/Product(size(i),i=1..n)-1, where size(i) denotes the size of subtree with root i.\nThen we have some observations:\n1. 
First, the answer can be expressed as n!/Product(size(i),i=1..n)-1, where size(i) denotes the size of subtree with root i.\nThen we have some observations:\n1. any node in subtree must be inserted after the root\n2. any subtree contains a consecutive interval\n3. after any insertion step, any remaining interval will finally form a subtree\n\nNow if we invert the insertion process, it becomes deleting nodes from a BST. The observations\n1. the root of a subtree is the last deleted node in that subtree\n2. any deleted subtree contains a consecutive interval\n3. after any deletion step, any removed interval form a subtree\n\nWhen a node p is deleted, both of its subtree are already deleted. And if p+1(or p-1) is deleted, it must belong to the right(or left) subtree of p. Otherwise their LCA is not deleted yet and must have value between them, which is impossible. So the deleted interval that contains p+1(or p-1) just forms the right(or left) subtree of p. Adding p to the set of deleted nodes will possibly connect two intervals or extend one interval, which corresponds to the two subtrees of p being non-empty or only one subtree being non-empty. Therefore, using a doubly linked list, we can easily merge intervals and calculate their length, which is the size of subtrees.\nTake [3,4,5,1,2] as an example:\nStep 0. complete BST, no deleted nodes yet\nThe doubly linked list is like 1--2--3--4--5\nStep 1. delete 2\nNow we know that the subtree with root 2 has size 1. The node itself form an interval.\nThe doubly linked list is now 1--[2,2]--3--4--5\nStep 2. delete 1\nWe find that 2 is already deleted, so we extend the deleted interval. Now we know that the subtree with root 1 has size 2. The two nodes form an interval.\nThe doubly linked list is now [1,2]--3--4--5\nStep 3. delete 5\nNow we know that the subtree with root 5 has size 1.\nThe doubly linked list is now [1,2]--3--4--[5,5]\nStep 4. delete 4\nNow we know that the subtree with root 4 has size 2.\nThe doubly linked list is now [1,2]--3--[4,5]\nStep 5. delete 3\nNote that both 2 and 4 are deleted, so we connect the two intervals with 3, and find that the subtree with root 3 has size 5.\nThe doubly linked list is now [1,5].\nNow we calculate the answer: 5!/(1x2x1x2x5)-1=5.\nThe inverse element of 1..n under modulo can be calculated in O(n), and there are n operations in doubly linked list each with O(1) time cost, so the overall time complexity is O(n).\n```\n#define MOD 1000000007\n\nclass Node {\npublic:\n    int size,flag;\n    Node *l,*r;\n    Node(int s=1,Node* a=NULL,Node* b=NULL):size(s),flag(0),l(a),r(b){}\n};\n\nclass Solution {\npublic:\n    int numOfWays(vector<int>& nums) {\n        int n=nums.size();\n        int inv[n+1];inv[1]=1;\n        long long s=1;\n        for(int i=2;i<=n;i++)\n        {\n            inv[i]=((long long)(MOD-MOD/i)*inv[MOD%i])%MOD;\n            s=(s*i)%MOD;\n        }\n        Node p[n+2];\n        for(int i=0;i<=n+1;i++)\n        {\n            p[i].l=p+i-1;\n            p[i].r=p+i+1;\n        }\n        for(auto it=nums.rbegin();it<nums.rend();it++)\n        {\n            Node& t=p[*it];t.flag=1;\n            if(t.l->flag){t.l->l->r=&t;t.size+=t.l->size;t.l=t.l->l;}\n            if(t.r->flag){t.r->r->l=&t;t.size+=t.r->size;t.r=t.r->r;}\n            if(t.size>1)s=(s*inv[t.size])%MOD;\n        }\n        return (s+MOD-1)%MOD;\n    }\n};\n```
[]