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
Output format
For each test case, print the number of permutations for each query in the next Q lines.
Constraints
1≤T≤2000001≤n≤2000001≤Q≤2000001≤l≤r≤n
For the first query, the lexicographically smallest substring is "bb", therefore, the number of permutations are only 2 ({1,2} and {2,1}).
For the second query, the lexicographically smallest substring is "aabb", therefore, the number of permutations are 4 ({1,2,3,4}, {1,2,4,3}, {2,1,3,4} and {2,1,4,3}).