给定一棵4n-1个结点的二叉树，其中每个非叶结点都有恰好两个子结点。非叶结点编号为1到2n-1，叶子结点编号为2n到4n-1。初始时，每个叶子结点上都没有数字。
定义一个 DFS 序是优美的，当且仅当按该 DFS 序将所有标有数字的叶子结点上的数字拼成一个序列时，该序列可以通过若干次消除相邻相同数字的方式得到空序列。例如,在下图中,若叶子结点 4,6上标有数字 1,叶子结点 5,7上标有数字2,则按 DFS序(1,4.2.7.3,5,6]将所有标有数字的叶子结点上的数字拼成的序列为[1,2,2,1]，可以通过消除相邻的2的方式得到[1,1],再通过消除相邻的1的方式得到空序列，因此该DFS序是优美的:而按 DFS序1,4,2,3,5,6,7]将所有标有数字的叶子结点上的数字拼成的序列为[1,2,1,2]，无法通过若干次消除相邻相同数字的方式得到空序列，因此该DFS序不是优美的。
给定n次操作，第i(1≤i≤n)次操作会选择两个没有数字的叶子结点，然后将这两个结点标上数字i。保证在每次操作后，存在至少一个优美的 DFS 序。你需要求出每次操作后的优美的DFS序的数量。由于案可能较大，你只需要求出答案对1.000,000,007 取模后的结果。
从文件tree.in中读入数据。 输入的第一行包含一个非负整数c，表示测试点编号。c=0表示该测试点为样例。 输入的第二行包含一个正整数n，表示二叉树的结点个数为4n-1。 输入的第i+2(1≤i<2n-1)行包含两个正整数li和ri，分别表示结点i的左右子结点。保证i<li，ri≤4n-1，且所有的li,ri互不相同。 输入的第 i+2n+1(1≤i<n)行包含两个正整数 ai,bi;，表示第之次操作选择的叶子结点的编号。保证 2n≤ai,bi<4n-1，且所有的 ai,bi互不相同。
输出到文件 tree.out中。 输出n行，其中第i(1<i<n)行包含一个非负整数，表示第i次操作后的优美的 DFS 序的数量对1.000,000.007取模后的结果。
0 2 4 2 3 7 5 6 4 6 5 7
8 4
0 6 2 3 4 21 22 23 5 11 6 8 7 9 12 13 10 18 14 15 16 17 19 20 12 13 14 15 16 19 17 18 20 21 22 23
2048 2048 2048 1024 512 512
【样例1解释】 该样例即【题目描述】中所示的例子。 第一次操作后，叶子结点4和6上标有数字1，叶子结点5和7上没有数字，因此按任意 DFS序拼成的序列均为[1,1]，即所有的2=8个DFS 序都是优美的。 第二次操作后，叶子结点4~7上分别标有数字1,2.1,2，因此共有4个优美的DFS序,分别为[1,4,2.3,6,5,7],[1,4,2,7,3,5,6],[1,2,3,6,5,7,4],[1,2.7,3,5,6.4]。
【样例 3】 见选手目录下的tree/tree3.in与tree/tree3.ans. 该样例满足测试点6~10的约束条件。
【样例 4】 见选手目录下的tree/tree4.in与tree/tree4.ans. 该样例满足测试点11,12的约束条件。
【样例 5】 见选手目录下的tree/tree5.in与tree/tree5.ans. 该样例满足测试点17~20的约束条件。
【样例 6】 见选手目录下的tree/tree6.in与tree/tree6.ans. 该样例满足测试点24,25的约束条件。
【数据范围】
