C. Кодовое слово
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Знаменитый скульптор Кикассо — ребляндский шпион!

Этим заголовком пестрят сегодня берляндские газеты. И теперь опальный скульптор находится в бегах. В этот раз маэстро нашёл убежище у вас, своего давнего друга. Как ни странно, у вас оказался защищённый бункер, который вы и предоставили скульптору. Вы установили для бункера такую систему защиты, что открыть его сможете лишь вы. Для этого необходимо решить задачу, простую для вас, но сложную для кого-либо ещё.

Раз в день бункер формирует очередное кодовое слово s. Когда кто-нибудь пытается войти в бункер, на мониторе появляется целое число n. В ответ нужно ввести другое число — остаток от деления на 109 + 7 количества слов длины n, состоящих из строчных английских букв, таких, что они содержат строку s в качестве подпоследовательности.

Подпоследовательностью строки a называют такую строку b, которая может быть получена из строки a удалением некоторого набора символов, возможно пустого. В частности, любая строка является своей подпоследовательностью. Например, строка «cfo» — это подпоследовательность строки «codeforces».

Вы не успели реализовать алгоритм, который генерирует правильные ответы и это нужно срочно исправить. Займитесь этим.

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

В первой строке находится целое число m (1 ≤ m ≤ 105) — количество событий, происходящих в тестовом наборе.

Во второй строке находится непустая строка s — строка, которая была сгенерирована бункером в текущий день.

В следующих m строках находятся описания событий. Описание начинается с целого числа t — типа события.

Если t = 1, то считайте, что наступил новый день и теперь используется новая строка s. В таком случае в той же строке находится новое значение s.

Если t = 2, то далее находится целое число n (1 ≤ n ≤ 105). Это событие означает, что для входа необходимо найти ответ для текущей строки s и числа n.

Сумма длин всех сгенерированных строк не превосходит 105. Все заданные строки состоят только из строчных букв английского алфавита.

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

На каждый запрос типа 2 выведите в отдельной строке искомое количество по модулю 109 + 7.

Пример
Входные данные
3
a
2 2
1 bc
2 5
Выходные данные
51
162626
Примечание

В тестовом примере к первому слову нам подходят слова вида "a?" и "?a", где ? — произвольный символ. Слов этих типов 26 в отдельности, но слово "aa" удовлетворяет обоим шаблонам, поэтому всего слов 51.