Назовем две строки \(s\) и \(t\) эквивалентными, если для любой строки \(u\) длины 2, количество вхождений \(u\) в \(s\) совпадает с количеством вхождением \(u\) в \(t\). Таким образом, строки « aaaba », « abaaa » и « baaab » попарно эквивалентны между собой (строка « aa » входит два раза, строка « ab » один раз, строка « ba » один раз, строка « bb » не входит как подстрока), а строки « abb » и « bba » — нет.

В этой задаче вам будут даны \(Q\) строк, состоящих из символов « a », « b » и « c », для каждой из которых надо будет посчитать количество эквивалентных им непустых строк, также состоящих из символов « a », « b » и « c ». Так как это количество может быть очень большим, то надо вывести его остаток при делении на \(10^9+7\).