Counting Subsequences in a Transformed String

Problem Statement

Chef has an array of integers. He transforms the array into a string by mapping each integer i (where 1 ≤ i ≤ 26) to the corresponding lowercase English letter (1 → 'a', 2 → 'b', ..., 26 → 'z'). Chef is then given several queries. Each query consists of two indices l and r (1-indexed) and a target string s. For each query, Chef is required to count the number of subsequences in the substring formed from the l^th character to the r^th character which match the target string s.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

The answer for each query should be computed independently.

The dynamic programming formulation used to count subsequences is based on the recurrence:

\(dp[i][j] = \begin{cases} dp[i-1][j-1] + dp[i-1][j] & \text{if } source[i-1]=target[j-1]\\ dp[i-1][j] & \text{otherwise} \end{cases}\)

It is given that the target string could be empty; in this case, there is exactly one subsequence (the empty subsequence).

inputFormat

The input is given in the following format:

 n
 a1 a2 ... an
 q
 l1 r1 s1
 l2 r2 s2
 ...
 lq rq sq

Here:

• n is the number of elements in the array.
• The second line contains n space-separated integers, where each integer represents an element of the array.
• q is the number of queries.
• Each of the next q lines contains two integers l and r representing the starting and ending indices (1-indexed), followed by a string s which is the target string. Note that s may be empty.

outputFormat

For each query, output a single integer on a new line representing the number of times the target string appears as a subsequence in the corresponding substring.

## sample

5
1 2 3 4 5
3
1 5 abc
1 3 ab
2 4 abc

1
1
0

</p>