Cho một chuỗi chữ thường \(s\). Mỗi lần thao tác bạn có thể chọn một vị trí \(p\) (\(1 \le p < |s|\)) và thực hiện một trong hai thao tác sau:

1. Tăng ký tự tại \(s_p\) lên 1 đơn vị theo bảng chữ cái, và giảm \(s_{p+1}\) đi 1 đơn vị.
2. Giảm ký tự tại \(s_p\) đi 1 đơn vị, và tăng \(s_{p+1}\) lên 1 đơn vị.

Chỉ thực hiện thao tác nếu cả hai ký tự sau thao tác vẫn là chữ thường ('a' đến 'z').

Hỏi sau vô số lần thao tác hợp lệ, có thể thu được bao nhiêu chuỗi khác nhau từ chuỗi ban đầu?

In ra kết quả modulo \(10^9 + 7\).

Định dạng vào

• Dòng đầu tiên: số nguyên \(T\) – số bộ test
• \(T\) dòng tiếp theo: mỗi dòng một chuỗi chữ thường \(s\)

Định dạng ra

• Với mỗi test, in ra một dòng – số lượng chuỗi khác nhau có thể nhận được (modulo \(10^9+7\))

Input

3
aaaaaaaaa
ya
klmbfxzb

Output

0
24
320092793

Giải thích

• "aaaaaaaaa" không thể chuyển đổi vì không có cách nào tạo thay đổi từ các ký tự giống nhau ở biên 'a'.
• "ya" có thể thực hiện nhiều thao tác → tạo 24 chuỗi hợp lệ.

Ràng buộc

• Với 30% dữ liệu: \(T = 1\), \(|s| \le 10\)
• Với 60% dữ liệu: \(T \le 10\)
• Với 100% dữ liệu:
  • \(T \le 10^4\)
  • \(1 \le |s| \le 100\)