평범한 문자열 문제

두 문자열 $s$와 $t$는 길이가 2인 모든 문자열 $u$에 대해 $u$가 $s$에 나타나는 횟수와 $t$에 나타나는 횟수가 같으면 동치라고 한다. 예를 들어 aaaba, abaaa, baaab는 서로 동치이다. aa는 두 번, ab와 ba는 각각 한 번 나타나고, bb는 나타나지 않는다. 반면 abb와 bba는 동치가 아니다.

이 문제에서는 a, b, c로만 이루어진 문자열 $Q$개가 주어진다. 각 문자열에 대해, 같은 문자로 이루어진 비어 있지 않은 문자열 중 그 문자열과 동치인 것의 개수를 구한다. 개수가 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다.

첫 줄에 소문제 번호 $G$가 주어진다. 예제 테스트에서는 $G = 0$이다.

둘째 줄에 정수 $q$ ($1 \le q \le 10^5$)가 주어지고, 이어서 a, b, c로 이루어진 문자열이 한 줄에 하나씩 $q$개 주어진다. 모든 문자열 길이의 합은 $10^6$을 넘지 않는다.

$q$개의 정수를 출력한다. 각 문자열에 대해 동치인 문자열의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.

abaa와 동치인 문자열은 abaa, aaba, baab이다.

abca와 동치인 문자열은 abca, bcab, cabc이다.

ccbca와 동치인 문자열은 ccbca와 cbcca이다.

bacc와 동치인 문자열은 bacc뿐이다.