Международная олимпиада по языкам
Международная олимпиада по языкам
На международной олимпиаде по языкам проходит стадия отбора. На этом соревновании каждый должен представить свой язык.
Мурад решил, что его язык интересный и участвует в отборе. В его языке имеются m букв (c1
, c2
, ..., cm
). Любое слово из этих букв существует в этом языке.
Для того чтобы язык выглядел более аккуратным, Мурад решил выстроить все его слова по порядку. Он расположил слова по порядку возрастания длин слов, а если длины строк совпадали, то в лексикографическом порядке.
Во время отбора всем членам жюри понравился язык Мурада, и они решили испытать его, дав Мураду задачу связанную с его языком. Мураду дали некоторое слово из его языка и попросили найти его порядок в построенной им последовательности слов.
Помогите Мураду в этом деле.
Ответ может быть очень большим, поэтому требуется найти остаток от деления ответа на число 280230412.
Входнын данные
В первой строке дано количество букв m (1 ≤ m ≤ 26) в языке Мурада. На следующей строке через пробел даны сами буквы в алфавитном порядке c1
, c2
, ..., cm
. В третьей строке дано слово S (1 ≤ |S| ≤ 106
) из языка Мурада (здесь через |S| обозначена длина строки S).
Выходнын данные
Выведите порядок слова S в построенной им последовательности слов, вычисленный по модулю 280230412.
Пояснение
В первом тесте слова в языке имеют вид: a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb,...
Во втором тесте слова в языке имеют вид: a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa,...
2 a b bba
13
3 a b c aa
4