Background

MS is a very NB teammate of Legendary Grandmaster DiDiDi, There are endless stories about how they won the championship in various Grand Prix.

One day after they won the championship in GP of Zhijiang, MS went to Zhijiang food street to find what to eat tonight, unexpectedly MS found a goldfish-catching stall at a food festival, and of course, he was eager to try it!

There is an event just today: the master has a lot of old nets that have deteriorated, which you can use to try to catch fish with only 1 chance. And If you can catch a goldfish, the master will give you a replacement of the net, which is a brand new one that can try to catch n goldfish! After successfully catching the fish with a brand new net, the master will give you another new brand new net, and the net in your hand will be returned to the master.

MS will try to catch a goldfish every second, he has a probability p of successfully catching a fish; if he fails to catch it, he can only wait for the next opportunity. Of course, he is not willing to admit defeat.

If the net breaks and the goldfish are not picked up, he will decisively spend c yuan for an old net. Since catching goldfish is too amusing, how much does MS expect to spend per second in $10^{114514}$ seconds?

You need to output the result modulo $10^9 + 7$

Input

The first line contains an integer $T(1 ≤ T ≤ 1000)$, representing the number of test cases.

Each of the following T lines contains $4$ integers $n, a, b, c (1 ≤ n ≤ 10^9, 1 ≤ a < b < 10^9, 1 ≤ c ≤ 10^9),$

indicating that a brand new net can attempt to catch $n$ times, with a probability $p = \frac{a}{b}$to catch a fish, it costs c to buy an old net.

Output

Each of the test cases outputs a number, indicating MS expects to spend per second

Samples

1
2 1 2 4

1

Note

For the first sample, MS has the following states per second:

   • old net in hand: If MS catches fish, he will get a new net; If doesn’t, he will buy an old net.

  • new net in hand, and it can still be used for

    – $2$ times: If MS catches a fish, the master will replace his net with a new one that can be used for $2$ times; If doesn’t, the net can still be used for 1 time.

    – $1$ time: If MS catches a fish, the master will replace his net with a new one that can be used for $2$ times; If doesn't, he will spend $1$ with the net you have, with spending c yuan.

It can be obtained by calculation that MS has a probability of $0.25$ per second within $10^{114514}$ seconds to buy a net, and expects to spend $1$ yuan.