Uzunluğu olan, 0, 1, 2, 3 və ? simvollarından ibarət sətri verilmişdir. Hər ? simvolu , , , rəqəmlərindən biri ilə əvəz olunmalıdır (müxtəlif təkrarlar müxtəlif rəqəmlərlə əvəz oluna bilər).
Rəqəmlərdən ibarət u_1 u_2 \ldots u_n sətri üçün yüksəliş dedikdə u_i = 0, u_j = 1, u_k = 2 və u_l = 3 şərtlərini ödəyən i < j < k < l indekslər dördlüyü nəzərdə tutulur. İndekslərin qonşu olması vacib deyil.
Alınan sətirdəki yüksəlişlərin sayı -ə bölünən əvəzetmələrin sayını hesablayın. İki əvəzetmə, əgər hansısa ? simvolu onlarda müxtəlif rəqəmlərlə əvəz olunubsa, fərqli sayılır. Cavab böyük ola biləcəyi üçün onu moduluna görə çıxarın.
Birinci sətirdə bir tam ədəd (1 \le t \le 10^5) — test hallarının sayı verilir.
Növbəti sətrin hər biri 0, 1, 2, 3 və ? simvollarından ibarət boş olmayan sətrini ehtiva edir.
Bütün sətirlərin ümumi uzunluğu 5 \cdot 10^5-i aşmır.
Hər test halı üçün bir tam ədəd — yüksəlişlərin sayı -ə bölünən əvəzetmələrin sayını moduluna görə çıxarın.
Nümunə 1
Birinci test halında heç bir ? simvolu ehtiva etmir və dəqiq bir yüksəlişə malikdir. ədədi -ə bölünmür, ona görə cavab -dır.
İkinci test halında bir ? simvolu ehtiva edir. Əgər o, , və ya ilə əvəz olunarsa, alınan sətirdə yüksəliş olmur, isə -ə bölünür. Əgər o, ilə əvəz olunarsa, alınan sətir 0123 olur və bir yüksəlişə malikdir. Deməli, cavab -dür.
Üçüncü test halında hər yüksəliş hər rəqəmin iki təkrarından birini istifadə edir, buna görə 2 \cdot 2 \cdot 2 \cdot 2 = 16 yüksəliş var və ədədi -ə bölünür. ? simvolu yoxdur, ona görə cavab -dir.
Dördüncü test halında dörd ? simvolundan ibarətdir, ona görə 4^4 = 256 əvəzetmə var. Yalnız 0123 sətrində yüksəliş var (dəqiq bir dənə), qalanlarında isə heç biri yoxdur, ona görə cavab -dir.
Beşinci test halında heç bir yüksəliş ehtiva etmir.