| Автор: | 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 | |
|
| 2 | |
|