Alluka rất thích chơi với các chuỗi! Cô bé có riêng một bảng đánh giá về giá trị của các ký tự trong bảng chữ cái như sau: 'a' có giá trị là 1, 'b' có giá trị là 2, 'c' có giá trị là 3… cứ lần lượt như vậy cho đến hết bảng chữ cái.

Dạo này, cô bé đang chơi trò tìm 'chuỗi đẹp'. Với cô bé, chuỗi đẹp là một chuỗi mà tổng giá trị các ký tự trong chuỗi chia hết cho giá trị của ký tự đầu tiên và cuối cùng. Ví dụ, chuỗi "aabbcc" được coi là một chuỗi đẹp vì tổng giá trị của chuỗi là 1 + 1 + 2 + 2 + 3 + 3 = 12 chia hết cho giá trị của ký tự 'a' và 'c' (1 và 3).

Nhận thấy có rất nhiều chuỗi đẹp trong các khoảng, Alluka muốn nhờ bạn giúp đỡ để có thể đếm được tất cả số lượng chuỗi đẹp từ đầu đến một chuỗi nào đó, với đầu chuỗi là một chuỗi gồm toàn chữ cái 'a' có độ dài bằng độ dài chuỗi đã cho. Biết rằng một chuỗi liên tục là bao gồm các chuỗi thoả mãn chuỗi sau lớn hơn chuỗi trước đúng một đơn vị. Ví dụ: một chuỗi liên tục từ "aay" đến "abc" gồm các chuỗi "aay", "aaz", "aba", "abb", "abc".

Lưu ý, chuỗi a nhỏ hơn chuỗi b khi tại vị trí ký tự đầu tiên a và b khác nhau, giá trị ký tự đó của chuỗi a nhỏ hơn b.

Input

• Dòng đầu tiên là số nguyên \(t (t \le 20)\) ứng với số bộ test.
• t dòng tiếp theo, mỗi dòng là 1 xâu kí tự với độ dài \(l (1 \le l \le 50)\) chỉ chứa các chữ cái thường.

Output

• Với mỗi test, in ra một số là kết quả của bài toán. Do kết quả có thể rất lớn, hãy mod kết quả cho 1e9+7.

Example

Input 1

2
aaf
abcfz

Output 1

2
2816

Giải thích: Test 1 có 2 chuỗi đẹp là "aaa" và "aab".