Гірлянда UCPC#13080

Гірлянда UCPC

4,5 секунди
256 мегабайтів

Організатори UCPC прикрашають зал змагань довгою гірляндою з ламп у формі літер. Гірлянда складає рядок довжини з великих латинських літер: -та лампа показує літеру s_i. Кожну лампу треба ввімкнути одним із трьох кольорів: синім, жовтим або білим.

Звісно ж, улюблене слово організаторів — UCPC. Входженням слова UCPC у гірлянду називається вибір чотирьох ламп на позиціях i_1 < i_2 < i_3 < i_4, які показують відповідно літери U, C, P, C (вибрані лампи не обов'язково стоять поруч). Розфарбуванням входження називається послідовність кольорів ламп i_1, i_2, i_3, i_4 саме в такому порядку.

Розфарбування всієї гірлянди називається узгодженим, якщо всі входження слова UCPC мають однакове розфарбування. Іншими словами, хоч як глядач прочитає слово UCPC у гірлянді, він завжди побачить ту саму послідовність кольорів. Зокрема, якщо UCPC узагалі не входить у гірлянду, то будь-яке розфарбування є узгодженим.

Порахуйте кількість узгоджених розфарбувань гірлянди. Два розфарбування вважаються різними, якщо хоча б одна лампа має в них різні кольори. Оскільки відповідь може бути великою, виведіть її за модулем .

Організатори розглядають кілька гірлянд, і відповісти на це запитання потрібно для кожної з них.

Вхідні дані

Перший рядок містить ціле число (1 \le t \le 10^6) — кількість гірлянд.

Кожен із наступних рядків містить рядок (1 \le |s| \le 10^6, де — довжина рядка ) — гірлянду. Гарантується, що гірлянда складається з великих латинських літер.

Сумарна довжина всіх рядків не перевищує 10^6.

Вихідні дані

Для кожної гірлянди виведіть в окремому рядку одне ціле число — кількість її узгоджених розфарбувань за модулем .

Приклади

Приклад 1

Loading
Loading

Примітка

У першій гірлянді прикладу слово UCPC входить чотири рази, на позиціях (1,2,3,4), (1,2,3,6), (1,2,5,6) та (1,4,5,6). Лампа є другою літерою останнього входження і четвертою літерою першого, тому обидві літери C слова мусять мати однаковий колір. Звідси всі лампи з літерою C мають один спільний колір, і обидві лампи з літерою P мають один спільний колір. Разом із кольором лампи це дає 3^3 = 27 узгоджених розфарбувань.

У другій гірлянді жодна лампа не може бути одночасно другою і четвертою літерою входження, тому дві літери C слова можуть мати різні кольори: лампи мають один спільний колір, лампи — один спільний колір, лампи — один спільний колір і лампи — один спільний колір, що дає 3^4 = 81 розфарбування.

У третій гірлянді слово UCPC не входить узагалі, тому всі 3^3 = 27 розфарбувань узгоджені.