Міжнародна олімпіада з мов#9034

Міжнародна олімпіада з мов

1 секунда

128 мегабайтів

Легка

На міжнародній олімпіаді з мов проходить етап відбору. Кожен учасник повинен представити свою мову.

Мурад вирішив, що його мова цікава, і бере участь у відборі. У його мові є $m$ букв ( $c_{1}, c_{2}, \dots, c_{m}$ c_1, c_2, \ldots, c_m). Будь-яке слово, складене з цих букв, існує в цій мові.

Щоб мова виглядала більш впорядкованою, Мурад вирішив впорядкувати всі слова. Він розташував слова за зростанням їх довжини, а якщо довжини збігалися, то в лексикографічному порядку.

Під час відбору всім членам журі сподобалася мова Мурада, і вони вирішили випробувати його, давши задачу, пов'язану з його мовою. Мураду дали певне слово з його мови і попросили визначити його позицію в побудованій ним послідовності слів.

Допоможіть Мураду в цьому завданні.

Відповідь може бути дуже великою, тому потрібно знайти залишок від ділення відповіді на число $280230412$ .

Вхідні дані

У першому рядку задано кількість букв $m$ ( $1 \leq m \leq 26$ 1 \le m \le 26) у мові Мурада. У наступному рядку через пробіл наведено самі букви в алфавітному порядку $c_{1}, c_{2}, \dots, c_{m}$ c_1, c_2, \ldots, c_m. У третьому рядку дано слово $S$ ( $1 \leq ∣ S ∣ \leq 1 0^{6}$ 1 \le |S| \le 10^6) з мови Мурада (тут $∣ S ∣$ позначає довжину рядка $S$ ).

Вихідні дані

Виведіть позицію слова $S$ у побудованій послідовності слів, обчислену за модулем $280230412$ .

Приклади

Приклад 1

Приклад 2

Примітка

У першому тесті слова в мові мають вигляд: a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, $\dots$

У другому тесті слова в мові мають вигляд: a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, $\dots$