Lily has a ring of buckets, numbered from to . Each bucket has capacity . She has a pouring bucket with capacity , and wants to fill all buckets completely without any overflow, that is, to exactly. Unfortunately, every time she tries to pour into a bucket, she spills a little, and unit is spilled into each adjacent bucket, with poured into her original bucket. Note that and are adjacent.
Lily wants to fill all of the buckets to capacity, but wants to have zero overflow. Being a genius, Lily already knows the answer, and challenges you to find it too.
However, Lily will quickly bore of you listing out the numbers, so she decides on the following formula. If is the number of times you must pour into the th bucket, Lily will choose an arbitrary number and ask you to compute . This number may be large, so Lily will be satisfied if you can output it modulo . Additionally, if there are multiple solutions, choose the one that has the lexicographically smallest value of .
Finally, Lily has a lot of buckets, so she will ask you questions, each with their own values of and . Can you answer them all?
For all subtasks:
Subtask 1 [1/15]
Subtask 2 [2/15]
Subtask 3 [3/15]
Subtask 4 [3/15]
Subtask 5 [3/15]
Subtask 6 [3/15]
No additional constraints.
The first line will contain , the number of questions.
The next lines will contain four integers each, .
Output lines. For each question, if it is impossible to fill all the buckets exactly to capacity, output
Otherwise, output the required integer as specified above. Don't forget to output it modulo .
Sample Input 1
1 4 4 1 100
Sample Output 1
Explanation for Sample Output 1
There is no way to fill all the buckets exactly.
Sample Input 2
1 3 4 2 7
Sample Output 2
Explanation for Sample Output 2
If we pour once into each bucket, we get a solution array
1 1 1. Then, our required value is:
Sample Input 3
1 999999 999999 5 8
Sample Output 3