Беси купила новый телефон. Кнопки на нём расположены так:
123
456
789
Беси может нажимать одну клавишу, две клавиши одновременно
(имеющие общую сторону, всего 12 комбинаций), 4 клавиши одновременно, которые
формируют квадрат (1245, 2356, 4578, or 5689).
Например, если телефонный номер 123659874, она может сэкономить время
следующим образом:
- Нажать 1 и 2 одновременно.
- Нажать 3.
- Нажать 6, 5, 9, 8 одноврменно.
- Нажать 7 и 4 одновременно.
Однако при нажатии нескольких клавиш одновременно, цифры могут
могут записаться в произвольном порядке. Например, после последнего нажатия
(7 и 4 одновременно) может получиться 123596847 или 213659874
По заданной последовательности цифр, вычислите количество телефонных номеров,
которые она может набрать, по модулю \(10^9+7\).
**Замечание: Время на тест для этой задачи 4s, в два раза больше чем обычно..**
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(T\) (
\(1\le T\le 10\)), количество независимых тестов.
Каждая из последующих \(T\) строк содержит непустую строку цифр от 1 до 9.
Гарантируется, что длина этой строки не превысит \(10^5\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого теста выведите количество телефонных номеров, которые Беси
может набрать по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1478
4455
5968
31313211
123659874
|
5
2
24
3
255
|