D. To Be Named
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$ that has digits from $$$0$$$ to $$$9$$$, A TBN is defined as a sorted subsequence of the a string.

The cost of building TBN in a string $$$s$$$ is the sum of $$${s_i}^a$$$ Where $$$s_i$$$ is used in the subsequence of the TBN.

In addition to the string $$$s$$$ you are given an integer $$$a$$$ and $$$q$$$ queries, In each query you are given two integers L and R, and you have to print the total cost of building every possible unique TBN of the string $$$s$$$ with the length between $$$l$$$ and $$$r$$$ (inclusive).

The length of the TBN is the number of digits used in it for example the TBN $$$1223$$$ has a length of $$$4$$$.

Two TBNs ($$$s$$$ and $$$t$$$) are different if at least one of the following conditions is met:

  • The length of $$$s$$$ doesn't equal the length of $$$t$$$.
  • The length of $$$s$$$ equals the length of $$$t$$$ and there is at least one index $$$i$$$ such that $$$s_i \neq t_i$$$.

Since the answer could be arbitrarily large, You have to print the answer modulo $$$m$$$, $$$(m \le 10^9+7)$$$.

Please note that $$$m$$$ isn't necessarily prime.

Input

The first line of input contains one integer $$$T$$$ $$$(1 \le T \le 1000$$$), the number of test cases.

The first line of each testcase contains three integers $$$n$$$, $$$m$$$ and $$$a$$$ $$$(1 \le n \le 4 \cdot 10^4 $$$) $$$(1 \le m \le 10^9 + 7 $$$) $$$(1 \le a \le 10^5$$$).

The second line of each testcase contains the string s. $$$(0 \le s_i \le 9)$$$ for every $$$(1 \le i \le n)$$$

The third line of each test case contains one integer q, The number of queries $$$(1 \le q \le 10^5)$$$.

Each of the following $$$Q$$$ lines contains two integers $$$l$$$ and $$$r$$$ $$$(1 \le l \le r \le n)$$$.

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases doesn't exceed $$$4 \cdot 10^4$$$ and $$$10^5$$$ respectively.

Output

For each query, you have to print one integer, The answer for the query modulo $$$m$$$.

Example
Input
2
2 1003 2
22
2
1 1
1 2
4 1000000007 1
1221
2
1 2
2 3
Output
4
12
12
18
Note

In the second test, the TBNs of length 1 and 2 are {1}, {2}, {11}, {12}, {22} with cost (1 + 2 + 2 + 3 + 4) = 12