Digits Behind a Letter Sum

A puzzle column prints an addition in which every digit has been replaced by a capital letter. The addends are the strings in words and the total is result. Count the ways to give each distinct letter a digit so that:

• different letters get different digits (the same letter always gets the same digit);
• a word of two or more letters never starts with the digit 0 (a one-letter word may be 0);
• the sum of the addends, read as decimal numbers, equals result.

Return the number of such letter-to-digit assignments. If there are more than 10 distinct letters, the answer is 0.

Examples

Input:  words = ["A", "A"], result = "B"
Output: 4
Explanation: A = 1, 2, 3 or 4 gives B = 2, 4, 6 or 8. A = 0 would make B = 0 as well,
which reuses a digit.

Input:  words = ["TO", "GO"], result = "OUT"
Output: 1
Explanation: 21 + 81 = 102 is the only way.

Input:  words = ["AB", "BA"], result = "CC"
Output: 32

Constraints

• 1 <= len(words) <= 5
• 1 <= len(w) <= 10 for every addend w, and 1 <= len(result) <= 11
• every string contains only the letters A to Z

Goals

• Search digit assignments column by column with a carry instead of trying every permutation
• Let each column force the result letter's digit so bad branches die early