Jack is doing a programming contest. There are problems in this contest and the contest will last a total of minutes. The -th problem will take Jack exactly 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 minutes if he decides that he definitely wants to solve problem and problem . More formally, Jack wants to determine the number of subsets of problems that contain problem and problem whose sum of solve times is less than or equal to . Since this number may be very large, output it modulo . 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 of these queries.
In all subtasks,
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [60%]
No additional constraints.
The first line contains three space-separated integers, .
The next line contains space-separated integers, .
The next lines contain three space-separated integers, .
Output lines. The -th line should contain the answer to the -th query.
3 90 2 20 30 40 1 2 50 1 3 90