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

• 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$$.