Cow Multiplication

Consider the following multiplication in vertical form:

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

We call such an expression a "Cow multiplication" if we can substitute each * with one digit from a given multiset of n digits (none of which is 0) such that the multiplication is arithmetically correct. In the above template, the first number (multiplicand) has 3 digits and the second number (multiplier) has 2 digits. Then, the first partial product is the product of the multiplicand and the ones digit of the multiplier and must be a 3‐digit number, the second partial product is the product of the multiplicand and the tens digit of the multiplier and must also be a 3‐digit number. When the second partial product is shifted one position to the left and added to the first partial product, the final product (which is a 4–digit number) is obtained.

Note that in American schools the partial products are computed as follows: the first partial product is obtained by multiplying the multiplicand by the units digit of the multiplier, and the second partial product is obtained by multiplying the multiplicand by the tens digit of the multiplier.

Your task is to count the number of valid "Cow multiplications" that can be constructed by assigning the given digits to the positions marked by * (each digit is used exactly once). None of the numbers in the final expression should have a leading zero.

Mathematically, if we denote the multiplicand as \(A\) (a 3–digit number) and the multiplier as \(B=10b_2+b_1\) (a 2–digit number with \(b_2\) as its tens digit and \(b_1\) as its ones digit), then the following must hold:

[ \begin{aligned} &100 \le A \le 999,\ &10 \le B \le 99,\ &P_1 = A \times b_1 ; \text{is a 3–digit number},\ &P_2 = A \times b_2 ; \text{is a 3–digit number},\ &A \times B = P ; \text{is a 4–digit number with } P = 10 \times P_2 + P_1. \end{aligned} ]

If the digits in the expression A, B, P1, P2, P (written in their respective formats with exactly 3, 2, 3, 3 and 4 digits) exactly match the given multiset then the expression is a Cow multiplication.

inputFormat

The input consists of two lines:

• The first line contains an integer n (which will always be 15, the total number of * in the template).
• The second line contains n digits separated by spaces. All digits are nonzero. Note that digits may repeat.

outputFormat

Output a single integer: the number of valid Cow multiplication expressions that can be constructed.

sample

15
1 1 2 2 3 3 4 4 5 5 5 5 5 6 9

1