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 |
|
|