A cryptarithm is a mathematical puzzle where the goal is to find the correspondence between letters and digits such that the given arithmetic equation consisting of letters holds true.

Given a cryptarithm as an array of strings crypt, count the number of its valid solutions.

The solution is valid if each letter represents a different digit, and the leading digit of any multi-digit number is not zero.

Example

• For crypt = ["SEND", "MORE", "MONEY"] the output should be 1 , because there is only one solution to this cryptarithm:

  0 = 0 , M = 1 , Y = 2 , E = 5 , N = 6 , D = 7 , R = 8

and S = 9 ( 9567 + 1085 = 10652 )

• For crypt = ["GREEN", "BLUE", "BLACK"] the output should be 12 , because there are 12 possible solutions.

• For crypt = ["ONE", "TWO", "THREE"] the output should be 0 , because there are no valid solutions.

Input/Output

• [execution time limit] 0.5 seconds (cpp)
• [memory limit] 1 GB
• [input] array.string crypt Array of three non-empty strings containing only uppercase English letters.

Guaranteed constraints:

• 1 ≤ crypt[i].length ≤ 35 .

• [output] integer The number of valid solutions.