D. RPS Club Activity
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ people in a room, and they are playing the $$$n$$$-person version of RPS (Rock, Paper, Scissors). There are three types of moves — rock, paper, and scissors. Rock beats scissors, paper beats rock, and scissors beat paper.

A round of the game works as follows:

  1. All people who are currently in the room simultaneously make a move. Every person has $$$a\%$$$ probability of making rock, $$$b\%$$$ probability of making paper, and $$$c\%$$$ probability of making scissors;
  2. If there are one or three distinct types of moves made by these people, the round ends, and no one exits the room;
  3. If there are two distinct types of moves, all people who made the losing move leave the room and never come back again. People who made the winning move stay in the room. Then the round ends.

The game ends when there is only one person in the room.

What is the expected number of rounds to be played in the game? Print this number modulo $$$10^9+7$$$. If the expected number can be arbitrarily large, print $$$-1$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — the number of test cases.

The only line of each test case contains four integers $$$n, a, b, c$$$ $$$($$$$$$1 \leq n \leq 2000$$$, $$$0 \leq a, b, c \leq 100$$$, $$$a+b+c=100$$$$$$)$$$ — the number of people in the room to begin with and the probabilities of making rock, paper, and scissors.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, output one line containing one integer — the expected number of rounds in the game.

Example
Input
5
2 0 50 50
2 25 25 50
3 25 25 50
1 30 30 40
10 100 0 0
Output
2
200000003
123809527
0
-1
Note

In the first test case, the probability for having $$$1$$$ round is $$$\frac{1}{2}$$$, the probability for having $$$2$$$ rounds is $$$\frac{1}{4}$$$, the probability for having $$$3$$$ rounds is $$$\frac{1}{8}$$$, and so on. Thus, the answer is $$$\sum_{i = 1}^{\infty}\frac{i}{2^i} = 2$$$.

In the second test case, it can be shown that the expected number can be written as $$$\frac{8}{5}$$$. It can be shown that $$$\frac{8}{5} \equiv 200000003 \pmod {10^9+7}$$$, so $$$200000003$$$ is printed.

In the third test case, it can be shown that the expected number can be written as $$$\frac{244}{105}$$$.