Xâu đối xứng là xâu khi đọc các kí tự từ trái sang phải giống với khi đọc các kí tự từ phải sang trái.

Nam có một xâu ~S~ gồm ~N~ chữ cái Latinh in thường. Nam sẽ thực hiện thử thách trong ~Q~ ngày, mỗi ngày Nam sẽ chọn ra một xâu con ~S_{l..r}~ (xâu con của ~S~ bắt đầu từ vị trí thứ ~l~ đến vị trí thứ ~r~) và hỏi Hải câu hỏi sau:

Định nghĩa tập ~P_{l..r}~ là tập chứa tất cả các xâu đối xứng có thể tạo bởi các kí tự của ~S_{l..r}~. Hải có thể sắp xếp lại thứ tự của các kí tự hoặc bỏ đi một số kí tự. Chìa khóa của một xâu ~S_{l..r}~ được định nghĩa là xâu đối xứng dài nhất thuộc tập ~P_{l..r}~. Nam muốn Hải tính xem xâu ~S_{l..r}~ có bao nhiêu chìa khóa.

Ví dụ, nếu ~S =~ madamimadam, ~l=4~, ~r=7~, khi đó:

~S_{l..r} =~ amim và ~P_{l..r} = \{~ a, m, i, am, ai, ma, mi, mm, ia, im, mam, mim ~\}~.

Và các chìa khóa của xâu amim là mam và mim.

Vì số lượng chìa khóa của một xâu có thể rất lớn, Hải muốn nhờ các bạn tính giúp kết quả của ~Q~ thử thách sau phép lấy dư khi chia cho ~10^9+7~.

Input

• Dòng đầu tiên chứa xâu ~S~.

• Dòng thứ hai chứa số nguyên dương ~Q~ là số ngày thử thách.

• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~l~ và ~r~ ~(1 \le l \le r \le N)~ đại diện cho xâu con ~S_{l..r}~ được chọn.

Output

Ghi ra ~Q~ dòng, mỗi dòng ghi ra kết quả của từng thử thách theo thứ tự.

Scoring

Sample Input 1

Week
2
1 4
2 3

Sample Output 1

2
1

Sample Input 2

Abab
1
1 4

Sample Output 2

2

Notes

Ở ví dụ thứ nhất, ở truy vấn thứ nhất:

~P_{1..4} = \{~ w, e, k, ee, ewe, eke ~\}~.

Các chìa khóa của xâu này là ewe, eke.