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ột số điện thoại là một dãy chữ số từ $1$ đến $9$. Bessie gõ số điện thoại của mình từ trái sang phải, mỗi lần nhấn gõ ra một đoạn liên tiếp các chữ số tiếp theo:

• Nhấn một phím đơn lẻ (ví dụ $5$): gõ ra đúng một chữ số.
• 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$): gõ ra hai chữ số tiếp theo, chính là hai phím đó nhưng theo thứ tự tùy ý.
• 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$): gõ ra bốn chữ số tiếp theo, chính là bốn phím đó nhưng theo thứ tự tùy ý.

Các phím trong cùng một lần nhấn đôi một khác nhau, nên mỗi lần nhấn gõ ra đúng số chữ số bằng số phím được nhấn, và chuỗi gõ ra luôn có cùng độ dài với số điện thoại.

Cho chuỗi chữ số mà Bessie đã gõ ra, hãy đếm xem có bao nhiêu số điện thoại khác nhau có thể là số điện thoại ban đầu của Bessie. Hai số điện thoại là khác nhau nếu chúng khác nhau ở ít nhất một vị trí chữ số.

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 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ụ