C. Махмуд и сообщение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Махмуд написал сообщение s длины n. Он хочет послать его своему другу Моазу как подарок на день рождения, потому что тот очень любит строки. Он написал сообщение на магической бумаге, но был очень удивлен, когда увидел, что некоторые буквы исчезли после написания. А все потому, что эта магическая бумага не разрешает символу номер i латинского алфавита находится в строке длиной более чем ai. Например, если a1 = 2, то невозможно использовать символ 'a' на этой бумаге в строке длиной 3 или более. Строку «aa» возможно написать, в то время как строку «aaa» — нет.

Махмуд решил разбить сообщение не несколько подстрок, и написать каждую из них на отдельном листке магической бумаги так, чтобы каждая подстрока удовлетворяла ограничению бумаги. Сумма длин подстрок должна быть равна n, и подстроки не должны накладываться друг на друга. Например, если a1 = 2, и Махмуд хочет отправить строку «aaa», он может разбить ее на подстроки «a» и «aa» и использовать 2 магических листка, или, например, на «a», «a» и «a» и использовать 3 магических листка бумаги. Он не может разбить сообщение на «aa» и «aa», т. к. сумма длин этих строк больше, чем n. Он может разбить сообщение на единственную подстроку, если она удовлетворяет ограничениям.

Подстрока строки s — это строка, состоящая из нескольких последовательных букв из строки s, например, строки «ab», «abc» и «b» являются подстроками строки «abc», в то время как «acb» и «ac» — не являются. Любая строка является подстрокой самой себя.

Пока Махмуд думал о том, как же разбить сообщение, Ехаб сказал ему, что существует много способов сделать это. После этого Махмуд задал вам три вопроса:

  • Сколько существует способов разбить сообщение на подстроки, при условии, что все подстроки удовлетворяют ограничениям магической бумаги, сумма их длин равна n, и они не накладываются? Вы должны вычислить ответ по модулю 109 + 7.
  • Какая наибольшая длина может быть у какой-то подстроки какого-то корректного разбиения?
  • На какое минимальное число подстрок можно разбить сообщение?

Два разбиения считаются различными, если множества позиций разбиений различаются. Например, разбиения «aa|a» и «a|aa» считаются различными разбиениями сообщения «aaa».

Входные данные

В первой строке находится целое число n (1 ≤ n ≤ 103) — длина сообщения.

Вторая строка содержит сообщение s длиной n, состоящее из строчных букв латинского алфавита.

Третья строка содержит 26 целых чисел a1, a2, ..., a26 (1 ≤ ax ≤ 103) — для каждой буквы максимальная длина подстроки, в которой может встречаться эта буква.

Выходные данные

Выведите три строки.

В первой строке выведите число способов разбить сообщение на подстроки и удовлетворить всем ограничениям по модулю 109  +  7.

Во второй строке выведите наибольшую длину подстроки среди всех подстрок всех возможных разбиений.

В третьей строке выведите минимальное число подстрок, на которое можно разбить сообщение.

Примеры
Входные данные
3
aab
2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Выходные данные
3
2
2
Входные данные
10
abcdeabcde
5 5 5 5 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Выходные данные
401
4
3
Примечание

В первом примере можно разбить сообщение тремя способами:

  • a|a|b
  • aa|b
  • a|ab

Самые длинные подстроки — «aa» и «ab» длины 2.

Наименьшее число подстрок — 2 в разбиениях «a|ab» и «aa|b».

Заметьте, что «aab» — некорректное разбиение, потому что буква 'a' встречается в подстроке длины 3, в то время как a1 = 2.