首先我们要搞清楚一件事情，为什么原题条件所给的一个序列能对应一棵BST？而为什么那棵BST又可以对应其他很多的序列？
第一步要知道，条件所给的一个序列，能构造出唯一的一棵BST。怎么做？比较基础的办法就是逐个点地加上去。第一个点是根节点。第二点放在根节点左边还是右边，取决于它与根节点的相对大小。第三个节点放在哪里？其实只要从根节点出发，每一步做比较，比根大就往右边走，比根小就往左边走，直到遇到一个空节点的位置就放置在哪里。从这个过程可以知道，这个序列对应了一棵确定的BST。
第二步要知道，给定了一棵BST，为什么可以有多种序列？我们仔细研究这个序列生成的本质，其实是因为“左右子树节点的向下生成允许交错并行”。
举个第二个样例：
3
1 4
2 5
对于根节点而言，它的左子树只能有一种序列[1,2]，它的右子树只能有一种序列[4,5]。但是对于整棵树而言的序列，除了根节点3必须放在第一个，序列的剩下部分只需要满足[1,2]与[4,5]的相对顺序不变即可。也就是
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]
[3,4,5,1,2]
我们看出，[1,2]和[4,5]的任意次序的交叠(interleave)都是可以的。这样总共产生了6种。
这6种如何计算出来？我们可以更一般地设计两个序列，第一个长度是m，第二个长度是n，求“保持各自相对顺序的任意交叠”序列有多少个？这其实是一个高中组合数学的中等题。我们在总共m+n个位置中，只要选择出其中m个位置填上第一个序列，那么其他一切都能确定下来：这m个位置如何填充必须依照序列一的顺序；剩下的n个位置自然就是给第二个序列，并且他们如何填充必须依照序列二的顺序。所以我们只需要做的就是从m+n个位置中挑选m个，也就是C(m+n,n)。
解决了这个问题，我们就可以知道对任意一棵树，如何计算它的序列的个数。我们可以先递归处理它的子树，计算它的左子树有L种序列，它的右子树有R种序列，那么每一对左右序列，我们又可以产生C(m+n,n)种交叠序列（也就是这棵树本身的序列）。所以答案就是LRC(m+n,n)，其中m是左子树序列的长度（也就是左子树的节点总数），n是右子树序列的长度（也就是右子树的节点总数）。
可见，本题的大框架就是一个递归。从底层节点算起，不断给上层节点提供数据。
边界条件是叶子节点，序列数必然是1.
另外，本题需要计算大组合数以及算它对大质数的模。我们这里抛开逆元的用法，采用一个更容易理解的算法。利用组合数的递推公式:C(m+n,n) = C(m+n-1,n) + C(m+n-1,n-1)。这样可以将大组合数分解为小组合数，直至边界条件是C(x,1) = x, C(x,0) = 1。对于加法的分拆，(a+b)%M = a% + b%M是可以放心使用的。