Counting Non-Decreasing Subsequences

Bessie recently participated in a USACO contest and encountered the following problem. Can you solve it too?

Given a sequence \(A_1, A_2, \ldots, A_N\) where each \(A_i\) is an integer in the range \(1 \ldots K\) (\(1 \le K \le 20\)) and \(1 \le N \le 5\times10^4\), process \(Q\) queries (\(1 \le Q \le 2\times10^5\)). Each query is specified by an interval \([L,R]\) (\(1 \le L \le R \le N\)). For each query, compute the number of non-decreasing subsequences in \(A_L, A_{L+1}, \ldots, A_R\) modulo \(10^9+7\).

A non-decreasing subsequence of a sequence \(A_L, A_{L+1}, \ldots, A_R\) is defined as a collection of indices \(j_1, j_2, \ldots, j_x\) where \(L \le j_1 < j_2 < \cdots < j_x \le R\) and \(A_{j_1} \le A_{j_2} \le \cdots \le A_{j_x}\). Remember to count the empty subsequence as well!

Hint: You might find it useful to model the subsequence selection as a state transition problem. Define states from \(0\) to \(K\) where state \(0\) means no element has been chosen yet. For each element \(a\) in the sequence, define a transition that always allows you to skip the element and, if possible, choose it (if \(a \geq \text{current state}\)). By combining these transitions (for example with a segment tree using matrix multiplication), you can answer queries efficiently by computing the product of transformations over the query interval.

inputFormat

The first line contains three integers \(N\), \(Q\), and \(K\).

The second line contains \(N\) integers \(A_1, A_2, \ldots, A_N\) where \(1 \le A_i \le K\).

Each of the following \(Q\) lines contains two integers \(L\) and \(R\), representing a query.

outputFormat

For each query, output a single integer representing the number of non-decreasing subsequences in the specified subarray \(A_L, A_{L+1}, \ldots, A_R\), modulo \(10^9+7\).

sample

3 2 3
1 2 3
1 1
1 3

2
8