Background

天有不测风云，人有旦夕祸福。

Description

一天, 上小学的妹妹跑过来问哥哥一道字母加法等式, 哥哥不假思索的便给出了一组可行解. 聪明的你发现, 一个字母等式可能有多种不同解, 于是你想编个程序计算一下.

Format

Input

输入包含多组数据.
每组数据第一行一个整数 n, 表示有 n 个字符串 3 ≤ n ≤ 10
接下来 n 行, 每行有1个最多只含10个大写字母的字符串, 前 n−1 行的字符串表示加数, 第 n 行的字符串表示和
每个样例最多只有10个互不相同的大写字母, 每个字母表示 0 − 9 中的一个数, 相同字母表示相同的数, 不同字母表示不同的数

Output

对于每组数据输出一个整数, 表示不同的可行解的数量.
对于两个可行解, 只要有一个字母表示不同的数字, 我们就认为这两个可行解不同

Sample

Input

4
TAI
SHEN
LA
ACER
3
SEND
MORE
MONEY

Output

76
1

Limitation

对于 30% 的数据, 满足最多有6个不同的大写字母
对于 100% 的数据, 满足最多有10个互不相同的大写字母
1s, 64000KiB for each test case.

Hint

Source

CDQZ TEST