Quem nunca virou a noite antes de uma prova importante? Especialmente quando há uma disciplina específica que você simplesmente não consegue entender… Essa é a situação de Carlos Brasil: ele está estudando para sua próxima prova, e há um certo tópico, representado por uma palavra-chave , que o assombra.
Ele precisa ler livros para a prova. Como lê muito rápido, ele pode representar o -ésimo desses livros por uma única string . Mas, como está com sono, ele começou a ter algumas alucinações, nas quais, para cada string , no máximo uma ocorrência da palavra-chave em fica destacada para ele.
Note que uma ocorrência de uma string em uma string é uma substring de que é igual a . Duas ocorrências de em são consideradas diferentes se ocorrem em posições diferentes em .
Tendo muito o que estudar, Carlos pensou em desistir e contar quantas alucinações diferentes possíveis ele poderia ter, respeitando a restrição de no máximo uma ocorrência de em . Duas alucinações são diferentes se uma ocorrência aparece em uma alucinação, mas não na outra (lembre-se do que significam ocorrências diferentes no parágrafo anterior).
No entanto, Carlos nunca desiste. Então cabe a você contar isso e satisfazer sua curiosidade! Como esse valor pode ser muito grande, imprima o resto da divisão por .
A primeira linha da entrada contém a palavra-chave , que é uma string de letras minúsculas latinas (a-z).
A segunda linha da entrada contém um inteiro : o número de livros.
A -ésima das linhas seguintes contém uma string de letras minúsculas latinas , representando o -ésimo livro.
É garantido que é no máximo .
Imprima uma única linha: o resto do número de alucinações possíveis que Carlos pode ter (considerando as restrições do problema) ao dividir por .
dp 3 naoseidp dpsdedpsdeamanha muitofacildpseitudodedpdpsvoufazerquestao
24
gaga 3 raraahahahromaromamagagaohlahlah gagagag togag
6
No primeiro livro, a palavra-chave ``gaga’’ ocorre uma vez, então a alucinação de Carlos pode destacar essa ocorrência ou não destacar nenhuma (2 possibilidades).
No segundo livro, ``gaga’’ ocorre duas vezes, começando em posições diferentes. Portanto, há 3 possibilidades: destacar a primeira ocorrência, destacar a segunda ocorrência ou não destacar nenhuma.
No terceiro livro, ``gaga’’ não ocorre, então há apenas 1 possibilidade.
Considerando todas as possibilidades de destaque para cada livro, obtemos o número total de alucinações possíveis: 2 ⋅ 3 ⋅ 1 = 6.
aaaaaaaaa 5 aaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a
95760