분해

문자열 $S$가 주어진다. 이 문자열을 비어 있지 않은 부분 문자열 여러 개(한 개도 가능)로 나눈다. 분할 방법은 $2^{|S|-1}$가지이다. 예를 들어 aba의 분할은 aba, ab+a, a+ba, a+b+a 네 가지이다.

부분 문자열 $T$의 가중치는 $T = x x \ldots x$를 만족하는 가장 짧은 문자열 $x$의 길이이다. 예를 들어 aaa의 가중치는 $1$이고, ab의 가중치는 $2$이다. 분할의 가중치는 분할에 포함된 모든 부분 문자열 가중치의 곱이다.

모든 분할의 가중치 합을 구하고, 그 값을 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \leq T \leq 10^5$)가 주어진다.

각 테스트 케이스는 한 줄에 소문자 알파벳으로 이루어진 문자열 $S$ ($1 \leq |S| \leq 2 \cdot 10^5$)가 주어진다. 모든 테스트 케이스의 $|S|$를 더한 값은 $10^6$ 이하이다.

각 테스트 케이스마다 답을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.