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

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

Мурад вирішив, що його мова цікава, і бере участь у відборі. У його мові є m букв (c[1], c[2], ..., c[m]). Будь-яке слово, складене з цих букв, існує в цій мові.

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

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

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

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

Вхідні дані

У першому рядку задано кількість букв m (1 ≤ m ≤ 26) у мові Мурада. У наступному рядку через пробіл наведено самі букви в алфавітному порядку c[1], c[2], ..., c[m]. У третьому рядку дано слово S (1 ≤ |S| ≤ 10^6) з мови Мурада (тут |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,...