D. The Great Angus Celebration
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the times of the Great Angus, when ancient recipes in the kingdom of "Burger King" were only starting to appear, each element of the array was treated as a separate ingredient for the sacred burger. The number $$$a_i$$$ meant which ingredient was on the $$$i$$$-th shelf of the royal storage, and there were $$$n$$$ shelves in total.

But on the day of the Great Angus Celebration, the priests were given an unusual task. From the segment of the storage from the $$$l$$$-th to the $$$r$$$-th shelf, they had to collect exactly $$$k$$$ baskets of ingredients, such that:

  • the ingredient from the $$$i$$$-th shelf must be in at most one basket;
  • in each basket, the $$$\operatorname{MEX}$$$ of the set of ingredients must be equal to $$$x$$$.

Here, $$$\operatorname{MEX}$$$ — is the smallest non-negative integer that is not in the chosen basket: it was considered the number of the missing ingredient in the great Angus recipe.

The priests of "Burger King" believed that if they count the number of ways to collect the baskets like this on a segment of the storage, then on that day the Angus will be especially juicy, and the kingdom will be full and happy.

That is exactly what the wise men do: for each query with segment borders $$$[l, r]$$$ and number $$$x$$$, they count how many ways there are to choose a set of $$$k$$$ pairwise non-intersecting subsequences $$$a_l, a_{l+1}, \ldots, a_r$$$ such that each subsequence has $$$\operatorname{MEX}$$$ equal to $$$x$$$.

Note that two subsequences are considered different if they consist of elements with different indices in the array $$$a$$$. For example, in the array $$$a = [0, 0, 0]$$$ on the segment $$$[1,3]$$$ there are $$$7$$$ non-empty subsequences with $$$\operatorname{MEX}$$$ equal to $$$1$$$.

You have to act as a wise man and count the number of such ways. Since this number can be very large, it is enough to print the answers modulo $$$10^9 + 7$$$.

Input

In the first line, three integers $$$n$$$, $$$q$$$ and $$$k$$$ are given ($$$1 \le n, q \le 100\,000$$$, $$$1 \le k \le \min{(n, 1000)}$$$) — the number of shelves, the number of queries, and the number of baskets, respectively.

In the second line, $$$n$$$ integers $$$a_i$$$ are given ($$$0 \le a_i \le n$$$) — the ingredients on the shelves.

Each of the next $$$q$$$ lines contains one query. It contains three integers $$$l_i$$$, $$$r_i$$$ and $$$x_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$1 \le x_i \le n$$$) — the segment borders and the required value of $$$\operatorname{MEX}$$$, respectively.

Output

Print $$$q$$$ lines. Each of them must contain one integer — the answer to the corresponding query modulo $$$10^9 + 7$$$.

Scoring

The tests for this problem consist of eight groups. Points for each group are given only if all tests of this group and all tests of some previous groups are passed. Please note that passing the sample tests is not required for some groups. The final score for each group is equal to the maximum score obtained for this group over all submissions.

SubtaskPoints$$$n$$$AdditionallyRequired subtasks
17$$$n \le 8$$$—S
24—$$$k = n$$$—
312—$$$a_i = 0$$$—
413$$$n \le 3\,000$$$$$$k = 1$$$—
514$$$n \le 3\,000$$$—S, 1, 4
616—$$$k = 1$$$4
713—$$$l_i = 1$$$, $$$r_i = n$$$—
821——S, 1–7
Examples
Input
3 2 2
0 1 0
1 3 1
2 3 2
Output
1
0
Input
6 3 1
0 1 2 3 4 5
3 6 1
1 4 2
1 6 6
Output
0
2
1
Input
8 8 2
0 1 2 0 0 1 2 1
1 6 1
4 5 1
4 4 1
2 5 2
1 8 3
1 8 2
1 8 1
4 7 2
Output
18
1
0
0
144
72
54
0