동물원 timer 1s memory 512MB

정올 동물원에는 많은 동물들이 있다.

대부분의 동물들은 아무런 일도 하지 않고 게으른 상태였으며 사육사 재민이는 이런 분위기가 마음에 들지 않았다.

그래서 재민이는 동물들에게 KMP 알고리즘을 가르치기로 했다.

재민 : 길이 L의 문자열 S가 주어진다면 O(L)의 시간에 실패함수 fail[]을 구할 수 있어요. 혹시 fail[]의 의미를 아는 동물 있나요?

판다 : fail[i]는 S를 1~i 까지 보았을 때 접두사와 접미사가 일치하는 최대 길이를 의미합니다.

재민 : 잘했어요! 혹시 예시를 줄 수 있나요?

판다 : S="abcababc"라고 하면 fail[5]=2입니다. "ab"는 "abcab"의 접두사이자 접미사이며 가장 긴 문자열입니다. 따라서 2에요. 같은 방식으로 fail[8]은 abc가 성질을 만족하는 가장 긴 문자열이므로 3이 됩니다.

재민이는 판다를 칭찬해주었다. 그리고 수업을 마치기 전, 동물들에게 한 가지 숙제를 내주었다.

재민이는 fail[] 대신 num[]을 정의해, 이를 구하는 것을 숙제로 냈다.

재민이의 정의에 따르면 num[i] (1<=i<=N)은 S를 1~i까지 보았을 때, 그 문자열에서 접두사와 접미사가 동일하고 둘이 '겹치지 않는' 것의 개수를 의미한다.

여기서 겹치지 않는다는 것은 S상에서 같은 문자를 동시에 포함하지 않는다는 의미이다.

가령 S="aaaaa"라고 하면, 접두사 "aaa"와 접미사 "aaa"는 동일하지만 S에서의 위치 상 둘 다 세 번째 a를 공유하므로 겹쳐 조건을 만족하지 않는다.

S="aaaaa"라고 하면 num[]은 0, 1, 1, 2, 2의 배열이 된다.

재민이는 숙제에 초콜릿을 상품으로 걸었다.

펭귄은 이 이야기를 듣고 눈이 반짝거리기 시작했다.

하지만 펭귄은 수업 내내 자서 문제를 풀 수가 없었고 귀여운 표정을 지으면서 당신에게 도움을 요청했다.

N개의 문자열 S가 주어지면 각 S에 대해 num을 구하는 프로그램을 작성해서 펭귄을 도와주자.

단, 출력량이 매우 많을 수 있으므로 N개의 num 배열을 전부 출력하는 대신 각 S마다 (num[i]+1)을 모두 곱한 값을 10억 7로 나눈 나머지를 출력하라.