Республиканская олимпиада по информатике 2009 года за 11 класс | Казахстанские олимпиады

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

Жома любит использовать длинные и сложные пароли. И, как это обычно бывает, он забыл... Забыл пароль от домашнего компьютера и теперь не может поиграть в новую 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