## Problem E. Equidistant strings ≡

• problems
• en ru
 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.

1 ≤ n ≤ 104.

### Sample tests

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

0.110s 0.024s 13