Stefan’s New Year’s resolutions

Task

Stefan has big plans for the year that just begun and among others, one of his plans is to improve his contest ratings.
While every competitive programmer dreams of this, he is perfectly aware that not everyone can achieve it.
Now he stumbled across an array that he received as a gift many years ago, together with a very old scroll containing the problem statement below.

You are given an array $V$ of $N$ positive integers, numbered from $0$ to $N-1$, inclusive.
You have to answer $Q$ queries: given $L$, $R$ and $K$, find the product of the largest $K$ values of $V_L, V_{L+1}, \ldots, V_{R-1}, V_R$.

Stefan realized that this is not a cakewalk question so now it's your turn to help him overcome this challenge and write a program that answers the queries for him.
Since the answers can be very big, you have to print them module $10^9 + 7$ (i.e. the reminder of the division by $10^9 + 7$).

Input data

The input file consists of:

• a line containing integers $N$, $Q$.
• a line containing the $N$ integers $V_{0}, \, \ldots, \, V_{N-1}$.
• $Q$ lines, the $i$-th of which consisting of integers $L_{i}$, $R_{i}$, $K_{i}$.

Output data

The output file must contain a single line consisting of the $Q$ integers $ans_{0}, \, \ldots, \, ans_{Q-1}$.

Constraints and clarifications

• $1 \le N, Q \le 200\,000$.
• $1 \le V_i \le 200\,000$ for each $i=0\ldots N-1$.
• $0 \le L \le R < N$ for each query.
• $1 \le K \le R - L + 1$ for each query.

Example

stdin

9 15
8 1 9 4 7 9 4 9 3
7 7 1
1 4 2
5 6 1
1 7 4
2 8 6
2 3 1
3 6 2
5 7 3
0 7 3
0 5 3
6 8 3
2 5 1
0 7 6
2 3 2
4 7 4

stdout

9
63
9
5103
81648
9
63
324
729
648
108
9
163296
36
2268

Explanation

For the second query of the sample case, the values between $1$ and $4$ are $[1,9,4,7]$, the $2$ largest values are $9$ and $7$ and their product is $63$.

For the fourth query of the sample case, the values between $1$ and $7$ are $[1,9,4,7,9,4,9]$, the $4$ largest values are $9$, $9$, $9$ and $7$ and their product is $5103$.