Знаменитый скульптор Кикассо — ребляндский шпион!
Этим заголовком пестрят сегодня берляндские газеты. И теперь опальный скульптор находится в бегах. В этот раз маэстро нашёл убежище у вас, своего давнего друга. Как ни странно, у вас оказался защищённый бункер, который вы и предоставили скульптору. Вы установили для бункера такую систему защиты, что открыть его сможете лишь вы. Для этого необходимо решить задачу, простую для вас, но сложную для кого-либо ещё.
Раз в день бункер формирует очередное кодовое слово s. Когда кто-нибудь пытается войти в бункер, на мониторе появляется целое число n. В ответ нужно ввести другое число — остаток от деления на 109 + 7 количества слов длины n, состоящих из строчных английских букв, таких, что они содержат строку s в качестве подпоследовательности.
Подпоследовательностью строки a называют такую строку b, которая может быть получена из строки a удалением некоторого набора символов, возможно пустого. В частности, любая строка является своей подпоследовательностью. Например, строка «cfo» — это подпоследовательность строки «codeforces».
Вы не успели реализовать алгоритм, который генерирует правильные ответы и это нужно срочно исправить. Займитесь этим.
Примечание
В тестовом примере к первому слову нам подходят слова вида "a?" и "?a", где ? — произвольный символ. Слов этих типов 26 в отдельности, но слово "aa" удовлетворяет обоим шаблонам, поэтому всего слов 51.