Cho một chuỗi ~s~ bao gồm các chữ cái tiếng Anh viết thường. Cho ~q~ truy vấn, chọn hai số nguyên ~l~ và ~r~, lấy chuỗi con ~s_{l...r}~ (chuỗi con của ~s~ từ chỉ mục ~l~ tới chỉ mục ~r~).

Hãy xem xét tất cả các palindrome có thể được tạo ra từ một số chữ cái từ chuỗi con ~s_{l...r}~ . Bạn có thể sắp xếp lại các chữ cái khi bạn cần. Một số palindrome này có chiều dài tối đa trong số tất cả các palindrome này.

Hai xâu palindrome được coi là khác nhau nếu độ dài khác nhau hoặc tồn tại ít nhất một vị trí khác nhau.

Yêu cầu: Hãy tìm ra có bao nhiêu chuỗi palindrome có độ dài tối đa?

Input

• Dòng đầu tiên chứa chuỗi ~s~ (~1 \le |s| \le 10^5~).

• Dòng thứ hai chứa một số nguyên ~q~ (~1 \le q \le 10^5~).

• Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách ~l_i, r_i~ (~1 \le l_i \le r_i \le |s|~), biểu thị cho giá trị ~l~ và ~r~ trong truy vấn thứ ~i~.

Output

• Đối với mỗi truy vấn, in ra một dòng chứa một số nguyên biểu thị câu trả lời. Vì kết quả có thể rất lớn, in phần dư khi lấy kết quả chia cho ~10^9 + 7~.

Subtask

• ~30\%~ số test có ~1 \le |s| \le 100, 1 \le q \le 1000, r_i - l_i \le 3~.

• ~30\%~ số test khác có ~1 \le |s| \le 100, 1 \le q \le 1000~.

• ~40\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

hello
2
2 5
3 4

Sample Output 1

2
1

Sample Input 2

bedaocontest
1
5 7

Sample Output 2

1

Note

Ở test ví dụ thứ nhất:

• Truy vấn thứ nhất có ~2~ xâu palindrome dài nhất thỏa mãn là: lol và lel.

• Truy vấn thứ 2 có ~1~ xâu palindrome dài nhất thỏa mãn là: ll.

Ở test ví dụ thứ hai:

• Truy vấn thứ nhất có ~1~ xâu palindrome dài nhất thỏa mãn là: oco.