На международной олимпиаде по языкам проходит стадия отбора. На этом соревновании каждый должен представить свой язык.

Мурад решил, что его язык интересный и участвует в отборе. В его языке имеются 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,...