Чотири сходинки#13107

Чотири сходинки

2,5 секунди
256 мегабайтів

Задано рядок довжини , що складається із символів 0, 1, 2, 3 і ?. Кожен символ ? треба замінити однією з цифр , , , (різні входження можна замінити різними цифрами).

Для рядка цифр u_1 u_2 \ldots u_n сходженням називається четвірка індексів i < j < k < l така, що u_i = 0, u_j = 1, u_k = 2 і u_l = 3. Індекси не обов'язково сусідні.

Порахуйте кількість замін, за яких кількість сходжень в отриманому рядку ділиться на . Дві заміни різні, якщо якийсь символ ? замінено в них різними цифрами. Оскільки відповідь може бути великою, виведіть її за модулем .

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 10^5) — кількість тестових випадків.

Кожен із наступних рядків містить непорожній рядок , що складається із символів 0, 1, 2, 3 і ?.

Сумарна довжина всіх рядків не перевищує 5 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — кількість замін, за яких кількість сходжень ділиться на , за модулем .

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку не містить символів ? і містить рівно одне сходження. Число не ділиться на , тому відповідь — .

У другому тестовому випадку містить один символ ?. Якщо замінити його на , або , отриманий рядок не має сходжень, а ділиться на . Якщо замінити його на , отримаємо рядок 0123, який має одне сходження. Отже, відповідь — .

У третьому тестовому випадку кожне сходження використовує одне з двох входжень кожної цифри, тож сходжень 2 \cdot 2 \cdot 2 \cdot 2 = 16, а ділиться на . Символів ? немає, тому відповідь — .

У четвертому тестовому випадку складається з чотирьох символів ?, тож замін 4^4 = 256. Лише рядок 0123 має сходження (рівно одне), а всі інші не мають жодного, тому відповідь — .

У п'ятому тестовому випадку не містить сходжень.