Một xâu \(S\) được đánh số từ \(1\) đến \(N\). Người ta sẽ tính mã Hash theo modun Mod dựa trên mã giả bài Hash \(1\). Yêu cầu của bài toán này là tính mã Hash trên đoạn \([L,R]\). Tức là:

\(Hash = 0;\)

\(for\ i = L \rightarrow R:\ Hash = Hash\ *\ 31\ +\ (S_i\ - 'a'\ +\ 1);\)

Yêu cầu

Gồm \(Q\) truy vấn, mỗi truy vấn gồm một đoạn \((L,R)\) và với mỗi cặp \((L,R)\) chúng ta cần phải in ra giá trị Hash the modun Mod trong đoạn \([L,R]\) đó.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương \(Mod\ (Mod \leq 10^9)\)
• Dòng thứ hai gồm một xâu \(S\ (|S| \leq 10000)\)
• Dòng thứ ba gồm một số nguyên dương \(Q\ (Q \leq 10^5)\)
• \(Q\) dòng tiếp theo, mỗi dòng gồm một cặp \((L,R)\ (L \leq R \leq N)\)

Kết quả

Gồm \(Q\) dòng, mỗi dòng là mã Hash theo modun Mod của đoạn \(S_L...S_R\)

Ví dụ