题目描述

我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的， 已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：

所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

输入格式

共两行，第一行表示该二叉树的前序遍历结果 s1 ，第二行表示该二叉树的后序遍历结果 s2 。 保证至少存在一棵二叉树满足给出的信息，s1,s2 中只含小写字母，且在某个字符串中不存在相同的字母。

输出格式

输出可能的中序遍历序列的总数，结果不超过 2^63-1。

样例

输入样例 1

abc
cba

输出样例 1

4

输入样例 2

abc
bca

输出样例 2

1

输入样例 3

abcdefg
cedbgfa

输出样例 3

4

提示

提示：观察图例可以发现，在知道前序、后序序列的情况下有不同的中序序列，只有当这个结点只有一个子结点。 例如前序中出现AB，后序出现BA，则这个A只有一个子结点B，统计满足这个条件的长度2的子序列的个数x。 每个这种序列的中序序列有2个，一棵树有x个这种序列，中序序列的数量就是2^x。