Задача E. Equidistant strings ≡

Условие

Рассмотрим множество всех возможных строк длиной ровно 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).

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁴.

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

abc
1b3

41688

ab
ab

1296