All Tracks>Problem
Permutations
★★★★★

3.5

11 votes
String Algorithms, Algorithms, Hashing Algorithm
Problem

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≤T≤2000001≤n≤2000001≤Q≤2000001≤l≤r≤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.
Sample Input
1
6
bbaacd
3
1 2
1 4
1 6
Sample Output
2
4
4
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

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}).

Contributers:
Editor Image

?