A大学ではIDの入力ミスが多発していた。
そこで、A大学は入力ミス防止のため新しいIDを発行することにした。
新しいIDには入力ミス防止のためにIDが正しいかどうかチェックする方法がある。
・全ての桁の数字の総和を求める。
・ただし、右端の桁を1番目として、偶数番目の桁の数字を2倍にする。
・2倍することによって数字が10以上になった時、1の位の数字と10の位の数字を加算した数字をその桁の数字とする。
・総和が10で割り切れれば正しいID、そうでなければ間違いとする。
例として、53579というIDをチェックする。
全ての桁の数字の総和を求めるので、
5 + 3 + 5 + 7 + 9
ただし、偶数番目の桁の数字を2倍にするので、
5 + 6 + 5 + 14 + 9
2倍することによって数字が10以上になった時、1の位の数字と10の位の数字を加算した数字をその桁の数字とするので、
5 + 6 + 5 + (1 + 4) + 9
以上より、総和は30となる。30は10で割り切れるので、53579は正しいIDである。
B君はA大学の大学生であり、新しいIDを発行してもらったが、IDの一部の桁を忘れてしまった。
しかし、忘れてしまった部分にどんな数字が入るか、いくつか候補を絞ることに成功した。
あなたの仕事は、B君のIDの正しい組み合わせが何通りあるかを求めることである。
入力は以下のフォーマットで与えられる。
n ID m a0 a1 ... am-1
nはIDの桁の数である。
IDの各桁には0~9の数字または忘れた桁であるということを示す'*'という文字が入る。
mは'*'に入る数字の候補の数である。
aiは'*'に入る数字の候補である。
入力は以下の制約を満たす
1 ≤ n ≤ 100,000
1 ≤ m ≤ 10
0 ≤ ai ≤ 9
1 ≤ '*'の数 ≤ 7
答えの値を1行に出力せよ
5 5*57* 2 3 9
1
15 2***9*2*6*1199* 9 0 1 2 3 4 6 7 8 9
478297