1423. 植树造林(20 分)

艺钰想要去植树造林,由于二叉树也是树,所以他决定根据二叉树的形状来植树(???)。

现在她知道了二叉树的前序遍历和后序遍历,那么一共有多少种同时符合该前序遍历和后序遍历的二叉树呢?

前序遍历,就是先输出根节点,再遍历树的左子树,最后遍历树的右子树。

后序遍历,就是先遍历树的左子树,然后再遍历树的右子树,最后再输出根节点。

输入

输入包含三行。

第一行为二叉数的结点个数 n1 \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

来源

2021 天梯赛选拔 / 蓝桥杯热身赛

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 185
通过 41