Size 0, 1, 2, 3 ve ? karakterlerinden oluşan, uzunluğu olan bir dizesi veriliyor. Her ? karakteri , , , rakamlarından biriyle değiştirilmelidir (farklı oluşumlar farklı rakamlarla değiştirilebilir).
Rakamlardan oluşan bir u_1 u_2 \ldots u_n dizesi için tırmanış, u_i = 0, u_j = 1, u_k = 2 ve u_l = 3 olacak şekilde i < j < k < l indis dörtlüsüdür. İndislerin ardışık olması gerekmez.
Elde edilen dizedeki tırmanış sayısı ile bölünebilen değiştirmelerin sayısını bulun. Herhangi bir ? karakteri farklı rakamlarla değiştirilmişse, iki değiştirme farklı kabul edilir. Cevap büyük olabileceğinden, onu moduna göre yazdırın.
İlk satırda bir tam sayı (1 \le t \le 10^5) — test durumlarının sayısı verilir.
Sonraki satırın her biri 0, 1, 2, 3 ve ? karakterlerinden oluşan boş olmayan bir dizesi içerir.
Tüm dizelerin toplam uzunluğu 5 \cdot 10^5 değerini aşmaz.
Her test durumu için bir tam sayı — tırmanış sayısı ile bölünebilen değiştirmelerin sayısını moduna göre yazdırın.
Örnek 1
Birinci test durumunda hiç ? karakteri içermez ve tam olarak bir tırmanışa sahiptir. sayısı ile bölünemez, bu yüzden cevap 'dır.
İkinci test durumunda bir ? karakteri içerir. Eğer bu karakter , veya ile değiştirilirse, elde edilen dizede tırmanış olmaz ve sayısı ile bölünebilir. Eğer ile değiştirilirse, elde edilen dize 0123 olur ve bir tırmanışa sahiptir. Dolayısıyla cevap 'tür.
Üçüncü test durumunda her tırmanış, her rakamın iki oluşumundan birini kullanır, bu nedenle 2 \cdot 2 \cdot 2 \cdot 2 = 16 tırmanış vardır ve sayısı ile bölünebilir. Hiç ? karakteri yoktur, bu yüzden cevap 'dir.
Dördüncü test durumunda dört ? karakterinden oluşur, bu nedenle 4^4 = 256 değiştirme vardır. Yalnızca 0123 dizesinde tırmanış vardır (tam olarak bir tane), diğerlerinde ise hiç yoktur, bu yüzden cevap 'tir.
Beşinci test durumunda hiç tırmanış içermez.