404017 - 前序后序难题

通常来说，不能通过前序和后序遍历序列确定一颗二叉树的中序遍历序列，例如图4.39所示的这4颗二叉树： 所有的这4颗二叉树都有着相同的前序和后序遍历序列。这个现象不仅在二叉树中存在，也同时在m叉树中普遍存在。

输入包含多组测试数据。每组包含一行，按照m，s1，s2的形式，表示这是一颗m叉树，s1是这颗树的前序遍历序列，s2是后序遍历序列，两个序列只包含小写字母。对于所有的测试数据，1≤m≤20，1≤s1≤26，1≤s2≤26。如果s1的长度为k（当然s2的长度也为k），那么序列中一定且只会出现前k个小写字母。当输入的一行只有一个数字0时，表示输入结束。

对于每组测试数据，需要输出一行，表示所给出的前序和后序遍历所表示的树一共有多少种可能。保证答案不会超过32位整型数据的范围。对于每种测试数据，保证至少存在一棵树满足所给出的前序和后序遍历序列。