/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
私は 10 進数のある正の整数を覚えておくように言われました。その数字は N 桁で、先頭の数字は 0 ではないです。
大事な数なのでメモ帳に 2 回書きました。
ところで私は文字を書くのが下手です。
後でメモ帳を読み返すと、メモ帳に書いた数字のうちいくつかについて、元はどの数字だったかわからなくなってしまいました。
元の数字がわからない文字は最大 26 文字で、以下では A から Z までの大文字アルファベットで表すことにします。これらの文字は、元は 0 から 9 までの 1 桁の数字のいずれかです。
メモ帳に書いた文字には、同じアルファベットが複数出てくるかもしれません。同じアルファベットが複数回出てきた場合、それらのアルファベットについてはいずれも元は同じ数字となります。1 回目に書いた文字列と 2 回目に書いた文字列に共通して登場するアルファベットが存在する場合もありますが、その場合でも、それらのアルファベットについて元は同じ数字となります。また、異なる種類のアルファベットの元の数字が同じ数字である場合も考えられます。
例えば、メモ帳の 1 回目の文字列が 1XYX であった場合、覚えておくように言われた数字としては 1101 (X = 1, Y = 0) や 1111 (X = 1, Y = 1), 1848 (X = 8, Y = 4) などが考えれますが、一方で例えば 1132 (Y = 3) は X に対する元の数字が 1 と 2 の複数種類存在するので、覚えておくように言われた数字としては考えられません。
メモ帳に書いた 2 つの文字列が与えられるので、覚えておくように言われた数字として全部で何通り考えられるかを求めるプログラムを作成してください。
入力
入力は以下の形式で標準入力から与えられる。
N s_1 s_2
- 1 行目には、覚えておくように言われた整数の桁数 N (1 ≦ N ≦ 18) が書かれている。
- 2 行目には、1 回目にメモ帳に書いた文字列 s_1 が与えられる。s_1 の長さはちょうど N 文字で、半角の大文字アルファベットと数字のみで構成されている。
- 3 行目には、2 回目にメモ帳に書いた文字列 s_2 が与えられる。s_2 の長さはちょうど N 文字で、半角の大文字アルファベットと数字のみで構成されている。
- 採点で用いられるすべての入力に関して、覚えておくように言われた整数として考えられる整数は少なくとも 1 つは存在する。つまり、どのようにアルファベットに数字を割り当てたとしても、s_1 と s_2 の最上位桁が 0 になってしまうか、s_1 と s_2 が異なる数字を表してしまう、ということはないものとして良い。
部分点
この問題には部分点が設定されている。
- N ≦ 6 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
- 追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。
出力
覚えておくように言われた整数として考えれられるものの個数を 1 行で出力せよ。出力の末尾にも改行を入れること。
なお、この問題での出力は 32-bit 整数に収まらない場合があることに注意せよ。
入力例1
4 1XYX 1Z48
出力例1
1
覚えているように言われた数としては 1848 (X=8, Y=4, Z=8) しか考えられません。
入力例2
3 XXX YYY
出力例2
9
先頭に 0 を使用できないことに注意してください。
入力例3
6 PRBLMB ARC027
出力例3
90