Mã Hash của xâu con

Cho xâu \(S = s_1 s_2 \ldots s_N\) gồm các chữ cái tiếng Anh in thường.

Mã Hash của xâu con \(s_L s_{L+1} \ldots s_R\) (\(1 \le L \le R \le N\)), kí hiệu \(H(L, R)\), là một số nguyên không âm nhỏ hơn \(10^9 + 7\) thỏa mãn: \(H(L, R) = H(X, Y)\) khi hai xâu con \(s_L \ldots s_R\) và \(s_X \ldots s_Y\) bằng nhau.

Để đáp án là duy nhất, mã Hash được tính theo công thức cụ thể sau (hàm băm đa thức cơ số \(31\)): gọi \(v(c)\) là thứ tự của chữ cái \(c\) trong bảng chữ cái (\(v(\texttt{a}) = 1, v(\texttt{b}) = 2, \ldots, v(\texttt{z}) = 26\)), khi đó

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên dương \(L\) và \(R\). Hãy tính giá trị của \(H(L, R)\).

Input

• Dòng đầu ghi xâu \(S\) gồm các chữ cái tiếng Anh in thường.
• Dòng thứ hai ghi số nguyên dương \(Q\).
• Trong \(Q\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(L\) và \(R\) (\(1 \le L \le R \le N\)).

Ràng buộc: \(1 \le N \le 300000\); \(1 \le Q \le 300000\).

Output

Gồm \(Q\) dòng, mỗi dòng ghi một giá trị \(H(L, R)\) tương ứng.

Sample Input 1

abba
6
1 1
4 4
2 2
3 3
1 2
3 4

Sample Output 1

1
1
2
2
33
63

Notes

\(H(1, 2) = v(\texttt{a}) \cdot 31 + v(\texttt{b}) = 31 + 2 = 33\); \(H(3, 4) = v(\texttt{b}) \cdot 31 + v(\texttt{a}) = 62 + 1 = 63\).