Dörd pillə#13107

Dörd pillə

2,5 saniyə
256 meqabayt

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.

Giriş

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.

Çıxış

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ələr

Nümunə 1

Loading
Loading

Qeyd

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.