Jack is doing a programming contest. There are ~N~ problems in this contest and the contest will last a total of ~T~ minutes. The ~i~-th problem will take Jack exactly ~t_i~ minutes to solve. Having an aversion to certain problem types such as dynamic programming, Jack wonders how many subsets of problems he can solve within ~q_i~ minutes if he decides that he definitely wants to solve problem ~a_i~ and problem ~b_i~. More formally, Jack wants to determine the number of subsets of problems that contain problem ~a_i~ and problem ~b_i~ whose sum of solve times is less than or equal to ~q_i~. Since this number may be very large, output it modulo ~10^9+7~. Two subsets are different if there is a problem in one of the subsets that does not appear in the other subset.

Help Jack answer a total of ~Q~ of these queries.

Constraints

In all subtasks,
~2 \le N, T, Q \le 2\,000~
~1 \le t_i, q_i \le T~
~1 \le a_i, b_i \le N~
~a_i \ne b_i~

Subtask 1 [20%]

~N, T \le 100~

Subtask 2 [20%]

~Q \le 10~

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains three space-separated integers, ~N~ ~T~ ~Q~.
The next line contains ~N~ space-separated integers, ~t_1, t_2, \dots, t_N~.
The next ~Q~ lines contain three space-separated integers, ~a_i~ ~b_i~ ~q_i~.

Output Specification

Output ~Q~ lines. The ~i~-th line should contain the answer to the ~i~-th query.

Sample Input

3 90 2
20 30 40
1 2 50
1 3 90

Sample Output

1
2