Số Điện Thoại

Bessie có một bàn phím số điện thoại với các số $1$-$9$ được sắp xếp trong lưới $3\times 3$:

• $$\begin{array}{ccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 3\hfill \\ \hfill 4\hfill & \hfill 5\hfill & \hfill 6\hfill \\ \hfill 7\hfill & \hfill 8\hfill & \hfill 9\hfill \end{array}$$

Mỗi lần nhấn, Bessie có thể:

• Nhấn một phím đơn lẻ (ví dụ: $5$).
• Nhấn hai phím liền kề (chia sẻ cạnh chung) cùng lúc (ví dụ: $1$ và $2$, hoặc $2$ và $5$).
• Nhấn bốn phím tạo thành hình vuông $2\times 2$ cùng lúc (ví dụ: $1,2,4,5$).

Khi Bessie nhấn nhiều phím cùng lúc, các chữ số tương ứng xuất hiện trong chuỗi đầu ra theo thứ tự tùy ý (bất kỳ hoán vị nào đều có thể xảy ra).

Cho chuỗi chữ số mà Bessie đã gõ ra, hãy đếm có bao nhiêu số điện thoại gốc khác nhau mà Bessie có thể đã cố gắng gõ để tạo ra chuỗi đầu ra này.

Hai số điện thoại gốc được coi là khác nhau nếu chúng khác nhau về số lần nhấn, hoặc ở một lần nhấn nào đó, tập phím được nhấn khác nhau.

Dữ liệu vào

• Dòng đầu tiên: số nguyên $T$ ($1\le T\le 10$), số lượng test case.
• $T$ dòng tiếp theo, mỗi dòng chứa một chuỗi không rỗng gồm các chữ số từ $1$ đến $9$.
• Tổng độ dài tất cả các chuỗi không vượt quá ${10}^5$.

Dữ liệu ra

Với mỗi test case, in ra số lượng số điện thoại gốc có thể, lấy dư cho ${10}^9+7$.

Ràng buộc

• $1\le T\le 10$
• Mỗi chuỗi chỉ chứa các chữ số $1$-$9$ và không rỗng.
• Tổng độ dài tất cả các chuỗi $\le {10}^5$.

Các cặp phím liền kề (chia sẻ cạnh):

• $(1,2),(2,3),(4,5),(5,6),(7,8),(8,9),(1,4),(2,5),(3,6),(4,7),(5,8),(6,9)$

Các bộ bốn phím hình vuông $2\times 2$:

• $\{1,2,4,5\},\{2,3,5,6\},\{4,5,7,8\},\{5,6,8,9\}$

Ví dụ

Ghi chú

Lưu ý rằng khi nhấn nhiều phím cùng lúc, các chữ số có thể xuất hiện theo bất kỳ thứ tự nào. Ví dụ, nhấn $\{7,8\}$ có thể tạo ra "78" hoặc "87" trong chuỗi đầu ra.