Cryptarithm?!

Time limit1sMemory limit128 MB

Summary

Given three letter strings A+B=C, decide whether some assignment of distinct digits to letters makes the addition valid, columns up to 18 long.

Level: Hard9 of 10
Topics: Backtracking, Math, Combinatorics, Brute force
Solved: No attempts yet

Problem

Cryptarithm is a mathematical puzzle in which each digit of a calculation is replaced by a letter, and the solver must recover which digit each letter stands for.

A well known instance is $SEND+MORE=MONEY$ .

  SEND
+ MORE
------
 MONEY

Setting $S=9$ , $E=5$ , $N=6$ , $D=7$ , $M=1$ , $O=0$ , $R=8$ , $Y=2$ satisfies the equation.

  9567
+ 1085
------
 10652

Given a cryptarithm $A+B=C$ written with three words, determine whether any digit assignment satisfies it.

The same letter always maps to the same digit, and different letters map to different digits. Numbers may start with $0$ .

Input

Three words $A$ , $B$ , $C$ are given, separated by spaces. They state that adding the first word and the second word yields the third word.

Each word consists only of uppercase English letters with no spaces, and each word is at most $18$ characters long.

Output

Print $YES$ on one line if any satisfying assignment exists, and $NO$ otherwise.

Hint

There can be many solutions, only existence matters. The input $SUN$ $FUN$ $SWIM$ admits $49$ solutions, including $067+867=0934$ and $167+867=1034$ .

Examples2

Example 1
Input
```
SUN FUN SWIM
```
Expected output
```
YES
```
Example 2
Input
```
P P AP
```
Expected output
```
NO
```