Республиканская олимпиада по информатике 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$.