GREAT + SWERC = PORTO

올해 포르투에서 열리는 SWERC를 잘 치르고 싶어서 여러 방법을 궁리했다. 그 가운데 하나가 대회 이름을 고전적인 SEND+MORE=MONEY 같은 낱말 덧셈 문제로 바꿔 보는 것이었다. 낱말 덧셈에서 각 글자는 0부터 9까지의 한 자리 숫자를 나타내고, 그 숫자를 대입했을 때 덧셈식이 성립해야 한다. 서로 다른 글자에는 서로 다른 숫자를 대입하며, 어떤 낱말이든 맨 왼쪽 글자는 0이 될 수 없다. 특히 글자가 하나뿐인 항도 0이 될 수 없다.

GREAT+SWERC=PORTO를 풀려면 G, S, P에 양의 숫자를 주고 R, E, A, T, W, C, O에도 숫자를 주어 모든 글자가 서로 다른 숫자를 갖고 덧셈이 맞아떨어지게 해야 한다. 해가 하나뿐인 SEND+MORE=MONEY와 달리 GREAT+SWERC=PORTO의 해는 여섯 개다.

• T=7, E=3, W=9, G=1, A=0, P=4, S=2, C=8, R=6, O=5
• T=7, E=3, W=9, G=2, A=0, P=4, S=1, C=8, R=6, O=5
• T=8, E=5, W=1, G=3, A=7, P=9, S=6, C=4, R=0, O=2
• T=8, E=5, W=1, G=6, A=7, P=9, S=3, C=4, R=0, O=2
• T=9, E=5, W=2, G=1, A=8, P=7, S=6, C=4, R=0, O=3
• T=9, E=5, W=2, G=6, A=8, P=7, S=1, C=4, R=0, O=3

해가 여럿이라 손으로 풀 문제로는 알맞지 않지만, 프로그램에게는 쉬운 일이다.

낱말 덧셈 문제가 주어지면 해의 개수를 구하라. 해가 하나도 없을 수도 있다.

첫 줄에 정수 $n$이 주어진다. 이어지는 $n$개의 줄에는 낱말이 한 개씩 주어지고, 낱말의 길이는 10 이하다. 앞의 $n-1$개는 더할 항이고 마지막 줄은 그 합이다. 낱말은 대문자로만 이루어진다. 길이가 서로 다른 낱말은 오른쪽 끝을 맞춰 정렬한 것으로 해석한다. 예를 들어 SEND+MORE=MONEY에서는 첫 낱말의 D와 둘째 낱말의 E가 마지막 낱말의 Y와 같은 자리에 온다. 마지막 낱말의 길이는 앞선 낱말 길이의 최댓값 이상이고, 한 문제에 나오는 서로 다른 글자는 10개 이하다.

주어진 낱말 덧셈 문제의 해의 개수를 정수 하나로 한 줄에 출력한다.

• $3 \le n \le 10$
• 각 낱말의 길이는 10 이하이고 대문자로만 이루어진다.
• 한 문제에 나오는 서로 다른 글자는 10개 이하다.