"Hon-te", "Myo-shu", "Zoku-shu", and "Kyo-shu" are four terms in Go. "Hon-te" refers to a standard, sound move that follows the principles of Go; "Myo-shu" refers to an unexpectedly brilliant move; "Zoku-shu" refers to a move that appears reasonable but is usually detrimental from a global perspective. A player should start with "Hon-te"; only after mastering the fundamentals of "Hon-te" can one improve their skill and play "Myo-shu", otherwise, one will inevitably play "Zoku-shu". However, when you are playing on your home turf and cannot find a "Myo-shu", you can also try to win directly by "Kyo-shu" (raising your hand).

Recently, Country H held a Go tournament and invited you to participate, and you have been winning all the way. To increase the difficulty of the tournament, Country H has introduced a new rule. After a player captures stones, they must place them into the lid of the Go bowl. If two or more stones are not successfully placed into the lid, you will immediately lose the game. We call these stones that fail to remain in the lid "out-of-bounds stones".

You are about to play the second round of the finals against a player from Country H. Since the opponent is a native of Country H, they can use the "Kyo-shu" method to further increase the difficulty of the game.

Formally, we can simplify the problem into the following scenario: The game consists of $n$ rounds, and each round strictly proceeds through the following stages in order. In any stage, if your total number of out-of-bounds stones reaches 2, or if the opponent successfully performs a "Kyo-shu", you will immediately lose the game.

1. At the beginning of a round, if you have exactly 1 out-of-bounds stone, the Country H player has a probability of $\frac{r}{1000}$ to perform a "Kyo-shu", causing you to lose immediately.
2. Afterward, you will receive a pile of $a_i$ stones. You will take the stones from this pile one by one and place them into the lid of the Go bowl until the pile is empty. Because you are too focused while thinking, each stone has a probability of $\frac{p}{1000}$ of being mishandled and not placed into the lid, becoming an out-of-bounds stone directly.
3. When placing a stone, if the total number of stones you have taken out previously is greater than or equal to 80 (regardless of whether they were eventually placed in the lid), then this newly placed stone has a probability of $\frac{q}{1000}$ of falling out of the overfilled lid, also becoming an out-of-bounds stone. During the above process, as soon as your total number of out-of-bounds stones reaches 2, you lose immediately.

Because you are very focused during the finals and are not familiar with this rule, you will not notice the stones that fall out of the lid, nor will you put them back.

Now, for each of the $n$ rounds, please calculate the probability that you lose exactly in this round due to the rules or the opponent's "Kyo-shu".

Input

The first line contains three non-negative integers $p, q, r$ ($0 \le p, q, r \le 1000$), representing the probability parameters of the rules.

The second line contains a positive integer $n$ ($1 \le n \le 10^5$), representing the number of rounds in the match.

The third line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), representing the number of stones captured in each round.

Output

Output $n$ lines, each representing the probability of losing in that round. If the probability is 0, output 0; otherwise, output $PQ^{-1} \pmod{10^9 + 7}$, where $\frac{P}{Q}$ is the irreducible fraction.

It can be proven that the probability of losing in each round is either 0 or can be expressed as $\frac{P}{Q}$ ($P, Q$ are coprime).

Examples

Input 1

0 500 1000
3
79 2 0

Output 1

0
0
500000004

Input 2

0 500 0
2
79 3

Output 2

0
250000002

Input 3

500 500 500
3
1 1 1

Output 3

0
375000003
531250004

Input 4

431 404 519
20
0 8 10 8 10 0 8 9 10 2 0 6 0 7 4 1 5 3 6 5

Output 4

0
65193629
491317294
880422337
670795490
121913119
186949131
942576908
924311201
247154371
759862879
967726799
679692511
202922928
490250649
551050329
827900501
946464281
916292188
461482115

Note

For Example 1, $p=0, q=\frac{1}{2}, r=1$. In the first round, you captured 79 stones, all of which were successfully placed in the lid. In the second round, the first stone you captured was successfully placed in the lid, and the second stone had a $\frac{1}{2}$ probability of not being placed in the lid. In this scenario, the opponent will definitely perform a "Kyo-shu" in the third round, so the probability of you losing in the third round is $\frac{1}{2}$.

For Example 2, $p=0, q=\frac{1}{2}, r=0$. In the first round, you captured 79 stones, all of which were successfully placed in the lid. In the second round, the first stone you captured was successfully placed in the lid, and the subsequent two stones each independently had a $\frac{1}{2}$ probability of not being placed in the lid. Therefore, the probability of you losing in the second round is $\frac{1}{4}$.

For Example 3, the probability of you losing in the second round is $\frac{3}{8}$, and the probability of losing in the third round is $\frac{9}{32}$.