Description

Below is a vertical multiplication. If we can replace each * with one of the given $n$ digits so that the equation is correct, we call it a "cow-style" multiplication.

          ***
    x      **
   ----------
         ***
        ***
   ----------
        ****

Digits may only replace *. The leading digit of any number cannot be $0$; besides, $0$ is not among the given digits.

Note the "partial products" as taught in U.S. schools: the first partial product is the product of the units digit of the second number and the first number; the second partial product is the product of the tens digit of the second number and the first number.

Compute the number of such "cow-style" cryptarithms.

Problem translation from NOCOW. USACO Training Section 1.4.

Input Format

The first line contains a positive integer $n$, the size of the available digit set.
The second line contains $n$ positive integers $a_i$, the available digits.

Output Format

Output a single line with one integer, the total number of cow-style cryptarithms.

5
2 3 4 6 8

1

Hint

Sample Explanation

          222
    x      22
   ----------
         444
        444
   ----------
        4884

No other digits are needed. This strictly follows the digit layout shown above, and it can be proved there are no other cases.

Without the sample explanation, solvers may misunderstand the statement and fall into traps, such as thinking the middle partial products need not be present or that the number of digits is unrestricted (e.g., wrongly accepting 34*2=68).

Constraints

For $100\%$ of the testdata, $1\le n \le 9$, $a_i \in [1,9] \cap \mathbb Z$, and all $a_i$ are distinct.

Translated by ChatGPT 5