동물원

얼마 전 동물원 사육사는 먹기만 하고 일은 하지 않는 동물이 늘고 있다는 사실을 알아차렸다. 펭귄을 보면, 귀여운 척을 해서 관람객에게 먹이를 받아내는 일에만 관심이 있다. 동물원의 안 좋은 분위기를 바로잡고 동물들이 진짜 재능을 보여 먹이를 얻도록 하기 위해, 사육사는 동물들에게 알고리즘을 가르치는 수업을 열기로 했다.

어느 날 사육사는 동물들에게 KMP 알고리즘을 강의하기로 했다.

사육사: "길이가 L인 문자열 S가 주어졌을 때, next[] 배열을 O(L) 시간에 만들 수 있다. next[]의 의미가 무엇인지 맞혀 볼 사람?"

판다: "문자열 S의 앞 i개 문자 안에서, 자기 자신은 제외하고 접두사이면서 접미사이기도 한 가장 긴 부분 문자열의 길이가 next[i]에 저장됩니다."

사육사: "잘했어! 예를 들어 설명해 줄 수 있니?"

판다: "S = abcababc이면 next[5] = 2입니다. 앞 5개 문자가 abcab이고, ab가 접두사이면서 접미사이고, 이 성질을 만족하는 더 긴 부분 문자열은 없기 때문입니다. 마찬가지로 next[1] = next[2] = next[3] = 0, next[4] = next[6] = 1, next[7] = 2, next[8] = 3입니다."

사육사는 판다의 성실함을 칭찬했다. 그리고 next[]를 O(L)에 계산하는 방법을 차근차근 설명했다.

수업을 마치기 전, 사육사는 문제를 하나 냈다. "KMP 알고리즘은 next[] 배열밖에 만들지 못한다. 우리는 더 강력한 num[] 배열을 얻고 싶다. 문자열 S의 앞 i개 문자 안에서, 접두사이면서 접미사이고 접두사와 접미사가 겹치지 않는 부분 문자열의 개수가 num[i]에 저장된다. 예를 들어 S = aaaaa이면 num[4] = 2다. S의 앞 4개 문자 aaaa에서 부분 문자열 a와 aa가 각각 '접두사이면서 접미사'라는 조건을 만족하고, 접두사와 접미사가 겹치지 않는다는 것도 보장한다. 부분 문자열 aaa는 '접두사이면서 접미사'라는 조건을 만족하지만, aaaa의 접두사이면서 동시에 접미사로서 자기 자신과 겹치므로 셀 수 없다. 같은 방식으로 num[1] = 0, num[2] = num[3] = 1, num[5] = 2임을 알 수 있다."

마지막으로 사육사는 상품을 걸었다. 가장 먼저 푸는 학생에게 초콜릿 한 상자를 주겠다는 것이었다. 이 말을 들은, 수업 내내 자고 있던 펭귄이 곧바로 깨어났다! 하지만 펭귄은 이 문제를 어떻게 풀어야 할지 전혀 모른다. 그래서 동물원 전체를 뒤져 너를 찾아왔다. 펭귄이 num[] 배열을 계산하는 프로그램을 작성하도록 도와줄 수 있겠는가?

구체적으로, 출력이 너무 커지는 것을 피하기 위해 num[i]의 값을 하나하나 출력할 필요는 없다. 대신 $\prod_{i=1}^{n}{num[i] + 1}$을 1,000,000,007로 나눈 나머지만 출력하면 된다.

첫째 줄에 테스트 케이스의 수 n이 주어진다.

다음 n개 줄에 각각 문제의 인스턴스 하나가 주어진다. 각 인스턴스는 문자열 S 하나로 이루어진다. S는 소문자로만 이루어져 있음이 보장된다.

입력에는 불필요한 공백이나 뒤쪽 공백이 없다.

출력은 n개 줄로 이루어지고, 각 줄은 대응하는 입력 문자열의 답이다. 답의 순서는 입력에서 문자열이 주어진 순서와 같아야 한다. 각 문자열의 답은 1,000,000,007로 나눈 나머지 하나의 정수다.

• 1 ≤ n ≤ 5
• 1 ≤ L ≤ 1000000