You are given a string s of length n.You are also given q queries of the form L R . For each query you have to find out the number of distinct strings that can be formed using the characters s_L,s_L+1,.......,s_R .

Since the answer can be very large print the answer modulo 10⁹ +7.

NOTE : All permutations of a string are considered same. For example : {"abc","acb","bac","bca","cab",cba"} all are considered same.

INPUT FORMAT

First line contains the length of the string n.

Second line contains the string s.

Third line contains the number of queries q.

Next q lines denote the queries ,each query containing two space separarted integers L and R.

OUTPUT FORMAT

For each query print the answer in a separate line.

CONSTRAINTS

 1$\leq$n$\leq$10⁵

 1$\leq$q$\leq$10⁵

1$\leq$L,R$\leq$n

String contains only lowercase english alphabets.