Verbal Arithmetic

時間制限 : 10 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem C: 覆面算

覆面算を考えよう.

このパズルでは,たとえば以下のような十進表現の非負整数の足し算を扱う.

    905 +  125 = 1030

覆面算では等式の中の全ての数字はアルファベットの文字で隠されている. たとえば,上で示した等式を答の一つに持つ問題には次のものがある.

    ACM + IBM = ICPC

このパズルを解くということは,与えられた覆面算において 各文字が隠している数字を見つけることである.

パズルの規則は以下のとおりである.

  • 整数の各桁は10種類の数字'0'〜'9'で表されるが,すべての数字は アルファベット文字'A'〜'Z'で隠されている.
  • 等式の複数箇所に現れる同一のアルファベット文字は,同じ数字を隠している. また,同じ数字はすべて,同じアルファベット文字で隠されている. すなわち,等式中の異なるアルファベット文字は異なる数字を表している.
  • ゼロが'0'という一文字で表される場合を除いて, 最上位の桁の数字は0になってはいけない. つまり,"00"や"0123"などの表現は許されない.

上の覆面算における可能な数字の割り当ては, 表に示す通り4種類ある.

MaskABCIMP
Case 1920153
Case 2930154
Case 3960157
Case 4970158

このパズルを解くプログラムを作成せよ.

Input

入力は複数のデータセットからなる. 入力の終わりはゼロをひとつだけ含む行で表される.

データセットの個数は100以下である. 各データセットは次の形式で表される.

N
STRING 1
STRING 2
...
STRING N

データセットの最初の行は,等式に現れる整数の数 N を表している.

それに続く N 行はそれぞれ,'A' 〜 'Z'というアルファベット大文字から成る1個の文字列を含む. これらのアルファベット文字が隠された数字を表している.

各データセットが表しているのは次の等式である.

STRING 1 + STRING 2 + ... + STRING N -1 = STRING N

N は 3 以上 12以下の整数, 各STRING i の長さは 1 以上 8 以下である. 各データセットに現れるアルファベット文字の種類は 1以上10以下である.

Output

等式を満たすような数字の割り当てが何通りあるかを, 各データセットに対してそれぞれ1行で出力しなさい.

それ以外の余計な文字を出力してはいけない.

Sample Input

3
ACM
IBM
ICPC
3
GAME
BEST
GAMER
4
A
B
C
AB
3
A
B
CD
3
ONE
TWO
THREE
3
TWO
THREE
FIVE
3
MOV
POP
DIV
9
A
B
C
D
E
F
G
H
IJ
0

Output for the Sample Input

4
1
8
30
0
0
0
40320

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2009-07-03
http://www.waseda.jp/assoc-icpc2009/en/