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

1T2000001n2000001Q2000001lrn

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

Editor Image

?