Problem E. Equidistant strings

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

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 format

Input contains two strings: A и B.

Output format

Output a single integer — the answer.

Constraints

1 ≤ n ≤ 104.

Sample tests

No. Standard input Standard output
1
abc
1b3
41688
2
ab
ab
1296

0.070s 0.009s 13