UCPC-nin təşkilatçıları yarış zalını hərf formasında lampalardan ibarət uzun bir qirlanda ilə bəzəyirlər. Qirlanda böyük latın hərflərindən ibarət uzunluqlu sətrini əmələ gətirir: -ci lampa s_i hərfini göstərir. Hər lampa üç rəngdən birində yandırılmalıdır: mavi, sarı və ya ağ.
Əlbəttə, təşkilatçıların sevimli sözü UCPC-dir. Qirlandada UCPC sözünün rastgəlməsi — uyğun olaraq U, C, P, C hərflərini göstərən i_1 < i_2 < i_3 < i_4 mövqelərindəki dörd lampanın seçimidir (seçilmiş lampaların qonşu olması vacib deyil). Rastgəlmənin rənglənməsi — i_1, i_2, i_3, i_4 lampalarının rənglərinin məhz bu ardıcıllıqla düzülüşüdür.
Bütün qirlandanın rənglənməsi, əgər UCPC sözünün bütün rastgəlmələri eyni rənglənməyə malikdirsə, uzlaşmış adlanır. Başqa sözlə, tamaşaçı qirlandada UCPC sözünün hansı rastgəlməsini oxumasından asılı olmayaraq, həmişə eyni rəng ardıcıllığını görəcək. Xüsusilə, əgər UCPC qirlandada ümumiyyətlə rast gəlinmirsə, onda istənilən rəngləmə uzlaşmışdır.
Qirlandanın uzlaşmış rəngləmələrinin sayını hesablayın. İki rəngləmə, ən azı bir lampanın rəngi onlarda fərqlidirsə, fərqli sayılır. Cavab böyük ola biləcəyi üçün onu moduluna görə çıxarın.
Təşkilatçılar bir neçə qirlandaya baxırlar və bu suala onların hər biri üçün cavab vermək lazımdır.
Birinci sətirdə tam ədədi verilir (1 \le t \le 10^6) — qirlandaların sayı.
Sonrakı sətrin hər biri bir sətri (1 \le |s| \le 10^6, burada — sətrinin uzunluğudur) — qirlanda ehtiva edir. Qirlandanın böyük latın hərflərindən ibarət olduğu təmin edilir.
Bütün sətrin ümumi uzunluğu 10^6-dan çox deyil.
Hər qirlanda üçün ayrıca sətirdə bir tam ədəd — onun uzlaşmış rəngləmələrinin sayını moduluna görə çıxarın.
Nümunə 1
Nümunədəki birinci qirlandada UCPC sözü dörd dəfə rast gəlinir: (1,2,3,4), (1,2,3,6), (1,2,5,6) və (1,4,5,6) mövqelərində. -cü lampa sonuncu rastgəlmənin ikinci hərfi və birinci rastgəlmənin dördüncü hərfidir, ona görə də sözün hər iki C hərfi eyni rəngdə olmalıdır. Buradan C hərfli bütün lampaların bir ümumi rəngi, P hərfli hər iki lampanın isə bir ümumi rəngi var. -ci lampanın rəngi ilə birlikdə bu, 3^3 = 27 uzlaşmış rəngləmə verir.
Nümunədəki ikinci qirlandada heç bir lampa eyni anda rastgəlmənin həm ikinci, həm də dördüncü hərfi ola bilməz, ona görə də sözün iki C hərfi müxtəlif rənglərdə ola bilər: lampalarının bir ümumi rəngi, lampalarının — bir ümumi rəngi, lampalarının — bir ümumi rəngi və lampalarının — bir ümumi rəngi var ki, bu da 3^4 = 81 rəngləmə verir.
Nümunədəki üçüncü qirlandada UCPC sözü ümumiyyətlə rast gəlinmir, ona görə də bütün 3^3 = 27 rəngləmə uzlaşmışdır.