| Author: | A. Baranov | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 512 Mb | |
| Output file: | Standard output |
Consider a set of all possible strings of exactly n characters, consisting of digits and small Latin letters.
Hamming distance H(A, B) is equal to the number of positions i from 1 to n
where A[i] ≠ B[i].
Let us define P(A, B) as a set of strings of length n equidistant from A and B
({ C: H(A, C) = H(B, C)}).
Determine the number of strings in the set P(A, B).
Since the answer may be too large, output the remainder of it divided by 109.
Input contains two strings: A и B.
Output a single integer — the answer.
1 ≤ n ≤ 104.
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
| 2 | |
|