P1211 [USACO1.3] Cow-Style Prime Cryptarithm

(This poorly named task has nothing to do with prime numbers or even, really, prime digits. Sorry about that.) A cryptarithm is usually presented as a pencil-and-paper task in which the solver is required to substitute a digit for each of the asterisks (or, often, letters) in the manual evaluation of an arithmetic term or expression so that the consistent application of the digits results in a proper expression. A classic example is this cryptarithm, shown with its unique solution: ``` SEND 9567 S->9 E->5 N->6 D->7 + MORE + 1085 M->1 O->0 R->8 ------- ------- MONEY 10652 Y->2 ``` The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set of $N$ digits into the positions marked with `*`. Since the asterisks are generic, any digit from the input set can be used for any of the asterisks; any digit may be duplicated as many times as desired. Consider using the set $\{2,3,5,7\}$ for the cryptarithm below: ``` * * * x * * ------- * * *

- Line 1: $N$, the number of digits that will be used. - Line 2: $N$ space separated non-zero digits with which to solve the cryptarithm.

A single line with the total number of solutions.

## Output Details Here is the one and only solution for the sample input: ``` 2 2 2 x 2 2 ------ 4 4 4 4 4 4 --------- 4 8 8 4 ``` Here is why `222x22` works: 3 digits times 2 digits yields two equal partial products, each of three digits (as required). The answer has four digits, as required. Each digit used $\{2,4,8\}$ is in the supplied set $\{2,3,4,6,8\}$. Why `222x23` does not work: ``` 2 2 2