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?

#### Constraints

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.

#### Input Specification

The first line will contain , the number of questions.

The next lines will contain four integers each, .

#### Output Specification

Output lines. For each question, if it is impossible to fill all the buckets exactly to capacity, output `-1`

.

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

`-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

`57`

#### 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

`35952588`

## Comments

Can someone please take a look at my code I spent a lot of time but I can't seem to find what is wrong? https://dmoj.ca/src/3377250

Ps I took a look at the editorial I think it has something to do with the big numbers. I think my logic is correct

Hint: compute , and then take it modulo .

Note that this number is not even. What does tell you about naively combining division and modulo operations?

Is there any good way to overcome this though, I tried to use the Modular inverse thing to find a solution But I am quite sure it doesn't work 100% of the time.

btw tysm for helping