Mật mã Sherlock

Cho một xâu $s$ gồm các chữ cái Latinh in thường. Trong một phép biến đổi, bạn chọn một vị trí $p$ với $1\le p<|s|$ và thực hiện một trong hai thao tác:

• Thay $s_p$ bằng chữ cái đứng ngay sau nó trong bảng chữ cái, đồng thời thay $s_{p+1}$ bằng chữ cái đứng ngay trước nó.
• Thay $s_p$ bằng chữ cái đứng ngay trước nó, đồng thời thay $s_{p+1}$ bằng chữ cái đứng ngay sau nó.

Chữ a không có chữ đứng trước, chữ z không có chữ đứng sau — nếu phép biến đổi yêu cầu một thay đổi không hợp lệ thì không được thực hiện.

Hai xâu được coi là tương đương nếu có thể biến đổi xâu này thành xâu kia bằng một dãy (có thể rỗng) các phép biến đổi.

Với mỗi xâu $w$ được cho, hãy đếm số xâu khác $w$ nhưng tương đương với $w$. In ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $t$ — số bộ dữ liệu.
• $t$ dòng tiếp theo, mỗi dòng chứa một xâu $w$ gồm các chữ cái Latinh in thường.

Dữ liệu ra

Với mỗi xâu, in ra trên một dòng số xâu khác nó nhưng tương đương với nó, theo modulo ${10}^9+7$.

Ràng buộc

• $1\le t\le {10}^4$.
• $1\le |w|\le 100$.
• Các xâu có thể có độ dài khác nhau.

Ví dụ