艺钰想要去植树造林,由于二叉树也是树,所以他决定根据二叉树的形状来植树(???)。
现在她知道了二叉树的前序遍历和后序遍历,那么一共有多少种同时符合该前序遍历和后序遍历的二叉树呢?
前序遍历,就是先输出根节点,再遍历树的左子树,最后遍历树的右子树。
后序遍历,就是先遍历树的左子树,然后再遍历树的右子树,最后再输出根节点。
输入
输入包含三行。
第一行为二叉数的结点个数 n ,1 \leq n \leq 100000 。
第二行为二叉树的前序遍历。
第三行为二叉树的后序遍历。
树的结点用互不相同的大于 0 的数字表示。
数字以空格间隔,保证至少有一种同时符合该前序遍历和后序遍历的二叉树。
输出
输出有多少种符合题意的二叉树,并且答案对于 1000000007 取模
样例
标准输入 复制文本 |
3 1 2 3 3 2 1 |
标准输出 复制文本 |
4 |
提示
样例1答案中四种不同的二叉树。
对于 4 分的数据,n \leq 10 。
对于 8 分的数据,n \leq 100 。
对于 12 分的数据,n \leq 1000 。
对于 16 分的数据,n \leq 10000 。
对于 20 分的数据,n \leq 100000 。