Республиканская олимпиада по информатике 2009 год

Задача C. Пароль

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Жома любит использовать длинные и сложные пароли. И, как это обычно бывает, он забыл... Забыл пароль от домашнего компьютера и теперь не может поиграть в новую NFS! Он очень расстроен и даже пару раз попытался вспомнить свой пароль. Но, увы, ничего не получилось. Однако он уверен, что при первой попытке он не ошибся ровно в $A$ символах, а при второй — ровно в $B$, но он не знает, какие именно символы были введены без ошибок. И тут его заинтересовало, сколько же паролей удовлетворяют заданным условиям?

Формат входного файла

Первая строка содержит первую попытку ввода пароля, вторая строка — вторую. Длины обеих строк одинаковы и равны $N$ ($1 \le N \le 10^5$). Каждая строка состоит только из строчных букв английского алфавита ('$a$'...'$z$'). Третья строка содержит число $A$, четвертая — $B$, $0 \le A, B \le N$.

Формат выходного файла

Выходной файл должен содержать ответ к задаче — остаток от деления количества возможных паролей на $10^9 + 7$.

Пример:

Вход

ab
ac
1
1

Ответ

24

Возможные пароли в примере: $aa$, $ad$, $ae$, ... $az$.