Задача E. Equidistant strings

Автор:A. Baranov   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Рассмотрим множество всех возможных строк длиной ровно n символов, состоящих из цифр и строчных букв латинского алфавита.

Расстояние Хэмминга H(A, B) равно количеству позиций i от 1 до n таких что A[i] ≠ B[i].
Определим P(A, B) как множество строк длины n, равноудаленных от A и B (C: H(A, C) = H(B, C)}).

Требуется определить количество строк в множестве P(A, B).

Так как ответ может оказаться слишком большим, выведите остаток от его деления на 109.

Формат входных данных

Входные данные содержат две строки: A и B.

Формат выходных данных

Выведите единственное целое число — ответ.

Ограничения

1 ≤ n ≤ 104.

Примеры тестов

Стандартный вход Стандартный выход
1
abc
1b3
41688
2
ab
ab
1296

1.838s 0.861s 15