Бесі купила новий телефон. Кнопки на ньому розташовані так:

123
456
789

Бесі може натискати одну клавішу, дві клавіші одночасно (мають спільну сторону, всього 12 комбінацій), 4 клавіші одночасно, які формують квадрат (1245, 2356, 4578, або 5689).

Наприклад, якщо телефонний номер 123659874, вона може заощадити час наступним чином:

1. Натиснути 1 та 2 одночасно.
2. Натиснути 3.
3. Натиснути 6, 5, 9, 8 одночасно.
4. Натиснути 7 та 4 одночасно.

Проте при натисканні кількох клавіш одночасно, цифри можуть можуть записатися у довільному порядку. Наприклад, після останнього натискання (7 та 4 одночасно) може вийти 123596847 або 213659874

За заданою послідовністю цифр, обчисліть кількість телефонних номерів, які вона може набрати, за модулем \(10^9+7\).

Примітка: Час на тест для цієї задачі 4s, вдвічі більше, ніж зазвичай.

Формат вхідних даних

Перший рядок містить \(T\) (\(1\le T\le 10\)), кількість незалежних тестів.

Кожен із наступних \(T\) рядків містить непустий рядок цифр від 1 до 9. Гарантується, що довжина цього рядка не перевищить \(10^5\).

Формат вихідних даних

Для кожного тесту виведіть кількість телефонних номерів, які Бесі може набрати за модулем \(10^9+7\).

Приклад вхідних даних

5
1478
4455
5968
31313211
123659874

Приклад вихідних даних

5
2
24
3
255

Для першого рядка Бесі може набрати будь-який із цих п'яти номерів:

1478
1487
4178
4187
1748

Наприклад, якщо Бесі намагається набрати 4187, вона може спробувати натиснути 1 і 4 одночасно, потім 7 та 8 одночасно. Або спочатку 1, потім 4 і 7 (з можливим набором 7 4 і потім 8). Всі інші комбінації наборів призведуть до одного з номерів, що вже виписані.

Для третього тесту, оскільки числа формують квадрат, Бесі може набрати будь-яку перестановку вхідний послідовності.

ОЦІНЮВАННЯ:

• У тестах 2-3 всі телефонні номери мають довжину не більше \(8\).
• У тестах 4-5, телефонний номер містить лише цифри 1, 2, 3.
• У тестах 6-7, телефонний номер не містить цифри 5.
• У тестах 8-9, телефонний номер містить лише цифри 5, 6, 8, 9.
• У тестах 10-12, сума довжин рядків не перевищить \(10^2\).
• У тестах 13-15, сума довжин рядків не перевищить \(10^3\).
• У тестах 16-18, сума довжин рядків не перевищить \(10^4\).
• У тестах 19-21 немає додаткових обмежень.

Автор: Nick Wu