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.
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 \neq b_i~
Subtask 1 [20%]
~N, T \le 100~
Subtask 2 [20%]
~Q \le 10~
Subtask 3 [60%]
No additional constraints.
The first line contains three space-separated integers, ~N~ ~T~ ~Q~
The next line contains ~N~ space-separated integers, ~t_1, t_2, \ldots t_N~
The next ~Q~ lines contain three space-separated integers, ~a_i~ ~b_i~ ~q_i~
Output ~Q~ lines. The ~i~-th line should contain the answer to the ~i~-th query.
3 90 2 20 30 40 1 2 50 1 3 90