Two friends David and Rojer were preparing for their weekly class-test.
The are preparing for the math test, but because of continuously adding big integers and solving equations they got exhausted. They decided to take break and play a game. They play a game which will help them in both(for having fun and will also help to prepare for math test).
There are N words and they have to find RESULT with the help of these words (just like they have N integers and they have to find integer RESULT=sum of N integers) . Since they are playing this game for the first time! They are not too good in this. Help them in finding weather their RESULT is correct or not.   
NOTE:- Total number of unique characters in N words are not greater than 10. All input words and RESULT are in UPPER-CASE only!
Refer Here for how to add numbers : https://en.wikipedia.org/wiki/Verbal_arithmetic
-----Input:-----
- First line consist of an integer N (total number of words).
- Next N line contains words with which they have to find RESULT.
- Last line consist of the RESULT they found.
-----Output:-----
If RESULT is correct print true else print false.
-----Sample Input:-----
3
THIS
IS
TOO
FUNNY  
-----Sample Output:-----
true
-----Constraints-----
- $2 \leq N \leq 10$
- $1 \leq Length of The word \leq 10$
- $1 \leq Length of The Result \leq 11$
# Solution link: https://leetcode.com/problems/verbal-arithmetic-puzzle/discuss/939496/Python-Optimizations-to-beat-TLE-Top-Down-DP-(93)


#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

import functools,collections
def isSolvable(words, result):

    @functools.lru_cache(None)
    def helper(i, total, nums):

        if i == len(chars):
            return total == 0

        if i - 1 in checkpoints:
            t = str(abs(total))[::-1]
            for j in checkpoints[i-1]:
                if (j < len(t)) and (t[j] != '0'):
                    return False

        for j in range(len(nums)):
            if (nums[j] == 0) and (chars[i] not in not_zero) and helper(i+1, total, nums[:j]+nums[j+1:]):
                return True
            elif (nums[j] != 0) and helper(i+1, total + nums[j] * mult[chars[i]], nums[:j] + nums[j+1:]):
                return True

        return False

    # 1. Check the lengths of each word and result
    longest_word = len(max(words, key = len))
    if (len(result) < longest_word) or (len(result) > longest_word + 1):
        return False

    # 2. Check if result is in words
    if result in words:
        return len(words) < 3 and all(word == result or len(word) == 1 for word in words)

    # 3. Leading letters cannot be zero unless the length of the word is 1
    not_zero = set((word[0] for word in words if len(word) > 1))
    if len(result) > 1: not_zero.add(result[0])

    # 4. Set of all letters
    chars = set(result + ''.join(words))

    # 5. Letters in words add to the total
    mult = {char:0 for char in chars}
    groups = collections.defaultdict(set)
    for word in words:
        for i,char in enumerate(reversed(word)):
            mult[char] += 10**i
            groups[i].add(char)

    # 6. And letters in result subtract from the total
    for i,char in enumerate(reversed(result)):
        mult[char] -= 10**i
        groups[i].add(char)

    # 7. Letters that add and subtract the same amount can be any number, so ignore them.
    chars = {char for char in chars if mult[char]}
    for g in groups:
        groups[g] = groups[g].intersection(chars)
    chars = list(chars)

    # 8. All letters that occur later in the word may affect letters ealrier in the word
    for g in range(1, len(groups)):
        groups[g] |= groups[g-1]
    chars.sort(key = lambda c: min(g for g in range(len(groups)) if c in groups[g]))

    # 9. Once a number has been assigned to all the letters in a group
    #    the digit in total at position 10**i must be zero for a solution to exist
    checkpoints = collections.defaultdict(list)
    seen = set()
    checked = set()
    for i,char in enumerate(chars):
        seen.add(char)
        for g in groups:
            if (g not in checked) and groups[g].issubset(seen):
                checked.add(g)
                checkpoints[i].append(g)

    return helper(0, 0, tuple(range(10)))

n = inp()
x = [input().strip() for i in range(n)]
y = input().strip()
ans = isSolvable(x,y)
if ans:
    print("true")
else:
    print("false")

# Solution link: https://leetcode.com/problems/verbal-arithmetic-puzzle/discuss/939496/Python-Optimizations-to-beat-TLE-Top-Down-DP-(93)


#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

import functools,collections
def isSolvable(words, result):

    @functools.lru_cache(None)
    def helper(i, total, nums):

        if i == len(chars):
            return total == 0

        if i - 1 in checkpoints:
            t = str(abs(total))[::-1]
            for j in checkpoints[i-1]:
                if (j < len(t)) and (t[j] != '0'):
                    return False

        for j in range(len(nums)):
            if (nums[j] == 0) and (chars[i] not in not_zero) and helper(i+1, total, nums[:j]+nums[j+1:]):
                return True
            elif (nums[j] != 0) and helper(i+1, total + nums[j] * mult[chars[i]], nums[:j] + nums[j+1:]):
                return True

        return False

    # 1. Check the lengths of each word and result
    longest_word = len(max(words, key = len))
    if (len(result) < longest_word) or (len(result) > longest_word + 1):
        return False

    # 2. Check if result is in words
    if result in words:
        return len(words) < 3 and all(word == result or len(word) == 1 for word in words)

    # 3. Leading letters cannot be zero unless the length of the word is 1
    not_zero = set((word[0] for word in words if len(word) > 1))
    if len(result) > 1: not_zero.add(result[0])

    # 4. Set of all letters
    chars = set(result + ''.join(words))

    # 5. Letters in words add to the total
    mult = {char:0 for char in chars}
    groups = collections.defaultdict(set)
    for word in words:
        for i,char in enumerate(reversed(word)):
            mult[char] += 10**i
            groups[i].add(char)

    # 6. And letters in result subtract from the total
    for i,char in enumerate(reversed(result)):
        mult[char] -= 10**i
        groups[i].add(char)

    # 7. Letters that add and subtract the same amount can be any number, so ignore them.
    chars = {char for char in chars if mult[char]}
    for g in groups:
        groups[g] = groups[g].intersection(chars)
    chars = list(chars)

    # 8. All letters that occur later in the word may affect letters ealrier in the word
    for g in range(1, len(groups)):
        groups[g] |= groups[g-1]
    chars.sort(key = lambda c: min(g for g in range(len(groups)) if c in groups[g]))

    # 9. Once a number has been assigned to all the letters in a group
    #    the digit in total at position 10**i must be zero for a solution to exist
    checkpoints = collections.defaultdict(list)
    seen = set()
    checked = set()
    for i,char in enumerate(chars):
        seen.add(char)
        for g in groups:
            if (g not in checked) and groups[g].issubset(seen):
                checked.add(g)
                checkpoints[i].append(g)

    return helper(0, 0, tuple(range(10)))

n = inp()
x = [input().strip() for i in range(n)]
y = input().strip()
ans = isSolvable(x,y)
if ans:
    print("true")
else:
    print("false")
