UCPC'nin düzenleyicileri yarışma salonunu harf şeklindeki lambalardan oluşan uzun bir çelenkle süslüyorlar. Çelenk, büyük Latin harflerinden oluşan uzunluğunda bir dizgisi oluşturur: -inci lamba s_i harfini gösterir. Her lamba üç renkten birinde yakılmalıdır: mavi, sarı veya beyaz.
Elbette, düzenleyicilerin en sevdiği kelime UCPC'dir. Çelenkte UCPC kelimesinin bir geçişi, sırasıyla U, C, P, C harflerini gösteren i_1 < i_2 < i_3 < i_4 konumlarındaki dört lambanın seçimidir (seçilen lambaların bitişik olması gerekmez). Bir geçişin renklendirmesi, i_1, i_2, i_3, i_4 lambalarının renklerinin tam olarak bu sıradaki dizilimidir.
Tüm çelengin bir renklendirmesi, UCPC kelimesinin bütün geçişleri aynı renklendirmeye sahipse tutarlı olarak adlandırılır. Başka bir deyişle, bir izleyici çelenkte UCPC kelimesinin hangi geçişini okursa okusun, her zaman aynı renk dizilimini görecektir. Özellikle, UCPC çelenkte hiç geçmiyorsa, o zaman herhangi bir renklendirme tutarlıdır.
Çelengin tutarlı renklendirmelerinin sayısını hesaplayın. İki renklendirme, en az bir lambanın renkleri onlarda farklıysa farklı kabul edilir. Cevap büyük olabileceğinden, onu moduna göre yazdırın.
Düzenleyiciler birkaç çelenk üzerinde düşünüyorlar ve bu soruyu her biri için yanıtlamanız gerekiyor.
İlk satırda bir tam sayısı verilir (1 \le t \le 10^6) — çelenk sayısı.
Sonraki satırın her biri bir dizgisi (1 \le |s| \le 10^6, burada — dizgisinin uzunluğudur) — çelengi içerir. Çelengin büyük Latin harflerinden oluştuğu garanti edilir.
Tüm dizginin toplam uzunluğu 10^6'yı aşmaz.
Her çelenk için ayrı bir satırda tek bir tam sayı — onun tutarlı renklendirmelerinin sayısını moduna göre yazdırın.
Örnek 1
Örnekteki birinci çelenkte UCPC kelimesi dört kez geçer: (1,2,3,4), (1,2,3,6), (1,2,5,6) ve (1,4,5,6) konumlarında. numaralı lamba son geçişin ikinci harfi ve birinci geçişin dördüncü harfidir, bu yüzden kelimenin her iki C harfi de aynı renge sahip olmalıdır. Dolayısıyla C harfli tüm lambalar ortak bir renge, P harfli her iki lamba da ortak bir renge sahiptir. numaralı lambanın rengiyle birlikte bu, 3^3 = 27 tutarlı renklendirme verir.
Örnekteki ikinci çelenkte hiçbir lamba aynı anda bir geçişin hem ikinci hem de dördüncü harfi olamaz, bu yüzden kelimenin iki C harfi farklı renklere sahip olabilir: numaralı lambalar ortak bir renge, numaralı lambalar — ortak bir renge, numaralı lambalar — ortak bir renge ve numaralı lambalar — ortak bir renge sahiptir, bu da 3^4 = 81 renklendirme verir.
Örnekteki üçüncü çelenkte UCPC kelimesi hiç geçmez, bu yüzden tüm 3^3 = 27 renklendirme tutarlıdır.