You are given a string $$S$$ containing only lowercase alphabet characters. You are also given $$Q$$ queries. In each query, you are given two integers $$l$$ and $$r$$. Consider a substring $$S'$$ of string $$S[l, r]$$. You are required to print the number of permutations of the substring $$S'$$ that are lexicographically smallest among all permutations of $$S'$$. Since the number can be very large, print it modulo \(1e9+7\).

Input format

The first line contains an integer $$T$$ denoting the number of test cases.
The first line of each test case contains an integer $$n$$ denoting the length of string $$S$$.
The second line of each test case contains a string $$S$$.
The third line of each test case contains an integer $$Q$$ denoting the number of queries.
Next $$Q$$ lines of each test case contain two space-separated integers $$l$$ and $$r$$.

Output format

For each test case, print the number of permutations for each query in the next $$Q$$ lines.

Constraints

\(1 \le T \le 200000\\ 1 \le n \le 200000\\ 1 \le Q \le 200000\\ 1 \le l \le r \le n\)

It is guaranteed that the sum of $$n$$ over $$T$$ test cases does not exceed $$1e6$$.
It is also guaranteed that the sum of $$Q$$ over $$T$$ test cases does not exceed $$1e6$$.