Mật khẩu

Mật khẩu là xâu kí tự có độ dài lớn hơn \(0\), phân biệt chữ hoa chữ thường và không chứa dấu cách. Từ mật khẩu ban đầu ta có thể tạo ra nhiều mật khẩu bằng cách hoán vị các kí tự của nó.

Yêu cầu: Tính số lượng mật khẩu khác nhau được tạo thêm từ mật khẩu đã cho (không tính chính mật khẩu ban đầu).

Input

Dữ liệu vào có cấu trúc:

• Dòng đầu tiên ghi số nguyên \(n\) là số lượng mật khẩu (\(0 < n \le 10^3\)).

• \(n\) dòng tiếp theo, mỗi dòng là một mật khẩu có độ dài không quá \(20\) kí tự.

Ràng buộc: Có \(50\%\) số test với \(n \le 100\).

Output

In ra \(n\) dòng, mỗi dòng ghi một số nguyên là phần dư của kết quả tính được với mật khẩu tương ứng khi chia cho \(10^9\).

Example

Input:

2
Aab
AAb

Output:

5
2

Note

Mật khẩu Aab tạo thêm được \(5\) mật khẩu: Aba, aAb, abA, bAa, baA.

Mật khẩu AAb tạo thêm được \(2\) mật khẩu: AbA, bAA.