Processing math: 100%

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

1n104.

Sample tests

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

0.087s 0.008s 13