描述

我们都熟悉二叉树的先序遍历、中序遍历和后序遍历。数据结构课程中的一个常见问题是，当给定中序遍历和后序遍历时，如何找到二叉树的先序遍历。或者，当给定中序遍历和先序遍历时，如何找到后序遍历。然而，一般情况下，无法仅凭给定的先序遍历和后序遍历确定树的中序遍历。考虑以下四棵二叉树：

    a   a   a   a
   /   /     \   \
  b   b       b   b
 /     \     /     \
c       c   c       c

这些树的先序遍历和后序遍历完全相同。这个现象不仅仅局限于二叉树，对一般的 $m$-叉树也适用。

输入

输入将包含多个问题实例。每个实例由一行形式为：

$m$ $s1$ $s2$

表示树是 $m$-叉树，$s1$ 是先序遍历，$s2$ 是后序遍历。所有遍历字符串都由小写字母组成。对于所有输入实例，$1 <= m <= 20$，且 $s1$ 和 $s2$ 的长度在 $1$ 到 $26$ 之间（包括 $1$ 和 $26$）。如果 $s1$ 的长度为 $k$（显然，$s2$ 的长度也是 $k$），则字符串中将使用字母表的前 $k$ 个字母。输入行 $`0`$ 结束输入。

输出

对于每个问题实例，你需要输出一行，包含可能形成该先序遍历和后序遍历的树的数量。所有输出值都在 $32$ 位有符号整数的范围内。对于每个问题实例，保证至少存在一棵树能够生成给定的先序遍历和后序遍历。

2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda
0

4
1
45
207352860

来源

East Central North America 2002