小项最近刚学习树的遍历，他觉得二叉树的递归遍历、通过遍历结果倒推树的结构这两个知识很抽象，所以他为了加强练习，自己画了很多树来练习树的遍历过程。小李有一次看到了小项画的树，差点笑死。原来是小项给节点的命名有重复。

不过这倒是启发了小李产生了一个新的问题，给定一个二叉树的中序遍历和后序遍历，节点的名称可能有重复，请问能构成多少种不同的二叉树。你可以帮帮他吗？

不同的树是指：如果两个树的根节点名称、左子树或者右子树只要其中有一个不同，那么两棵树视为不同的树。如果两个树的根节点名称、左子树或者右子树均相同，那么两棵树视为相同的树。

从文件tree.in中读入数据。每个测试点包含多组测试数据。

输入第一行包含一个正整数 t，表示测试数据的组数。

每组测试数据包括两行字符串s_1、s_2，字符串仅由大写字母组成，分别表示二叉树的中序遍历和后序遍历。

输出到文件tree.out中。每组测试数据包括一行，每行输出仅一个数字，即能构成多少种不同的二叉树。结果可能很大，请输出其除以{10}^9的余数。

测试数据1的树只有一种，如下图。

测试数据2因为第一个字符串有1个字母‘A’,0个字母‘D’,而第二个字符串有2个字母‘A’，无论如何也不会产生符合条件的二叉树。

测试数据3的树有4种，如下图。

字符串长度不超过100，测试数据组数不超过10组

原创