Задано рядок довжини , що складається із символів 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
У першому тестовому випадку не містить символів ? і містить рівно одне сходження. Число не ділиться на , тому відповідь — .
У другому тестовому випадку містить один символ ?. Якщо замінити його на , або , отриманий рядок не має сходжень, а ділиться на . Якщо замінити його на , отримаємо рядок 0123, який має одне сходження. Отже, відповідь — .
У третьому тестовому випадку кожне сходження використовує одне з двох входжень кожної цифри, тож сходжень 2 \cdot 2 \cdot 2 \cdot 2 = 16, а ділиться на . Символів ? немає, тому відповідь — .
У четвертому тестовому випадку складається з чотирьох символів ?, тож замін 4^4 = 256. Лише рядок 0123 має сходження (рівно одне), а всі інші не мають жодного, тому відповідь — .
У п'ятому тестовому випадку не містить сходжень.