GeometryFeng's friend, Xiao Han, is playing a game called "Hollow Knight". Xiao Han thinks he is very lucky and has just finished playing the second game in the series, "Hollow Knight: Silksong". However, Xiao Han does not know that GeometryFeng has already been lucky for five whole years and still hasn't played "Silksong".

Xiao Han has reached the "Temple of the Black Egg" in the game. This mode is extremely difficult; Xiao Han needs to defeat $n$ bosses in a row to clear it. Now, he wants you to help him calculate the expected number of attempts to clear it.

The specific rules are as follows:

1. Xiao Han's initial health is $h$. Starting from the beginning, after successfully defeating $k$ bosses, there is a rest point where Xiao Han's health is fully restored.
2. For each boss, Xiao Han has a probability of being instantly killed by the boss. The probability of being instantly killed depends on his current health. When at full health, the probability is $p_i$, and for each point of health lost, this probability increases by a factor of $x$.
3. If Xiao Han is instantly killed by the $i$-th boss, the current attempt fails. Otherwise, he has a probability $q_i$ of taking damage, losing 1 point of health. If his health drops to 0, the attempt also fails.
4. Every time an attempt fails, he must start over from the beginning (i.e., the first boss). The attempt is successful only if he defeats all $n$ bosses and his health is not 0.

Input

The first line contains four integers $n, h, k, x'$ ($1 \le n \le 5 \times 10^4$, $1 \le h \le 5 \times 10^4$, $0 \le k < n$, $100 < x' \le 200$), where $x = \frac{x'}{100}$. Specifically, $k=0$ means there are no rest points.

The second line contains $n$ integers $q'_i$ ($0 \le q'_i < 100$), where $q_i = \frac{q'_i}{100}$ is the probability that Xiao Han takes damage from the $i$-th boss.

The third line contains $n$ integers $p'_i$ ($1 \le p'_i < 100$), where $p_i = \frac{p'_i}{100}$ is the probability that Xiao Han is instantly killed by the $i$-th boss when at full health.

The data guarantees that the probability of Xiao Han being killed is not 0.

Output

Output a single integer representing the expected number of attempts to clear the game, modulo $10^9 + 7$.

Formally, the answer modulo $10^9 + 7$ is expressed as $\frac{p}{q}$. Let $M = 10^9 + 7$. It can be proven that the answer can be represented as an irreducible fraction $\frac{p}{q}$ where $p$ and $q$ are integers and $q \not\equiv 0 \pmod M$. You need to output $p \cdot q^{-1} \pmod M$. In other words, you need to output the integer $x$ such that $0 \le x < M$ and $x \cdot q \equiv p \pmod M$.

Examples

Input 1

3 10 0 150
0 0 0
50 50 50

Output 1

8

Input 2

1 1 0 101
25
50

Output 2

666666674

Input 3

3 2 2 150
50 50 50
10 10 10

Output 3

899138140

Input 4

2 2 1 200
60 60
50 50

Output 4

4

Note

For the first example, the probability of being instantly killed by a boss when at full health is $\frac{50}{100}$, and the probability of taking damage is 0. There are no rest points, so the probability of clearing is $\left(1 - \frac{50}{100}\right)^3 = \frac{1}{8}$, so the expected number of attempts is 8.

For the second example, there is only one boss. Xiao Han has a $\frac{50}{100}$ probability of being instantly killed, otherwise, he has a $\frac{25}{100}$ probability of taking damage and losing 1 point of health. At this point, his health becomes 0, which also results in failure. Thus, the probability of clearing is $\left(1 - \frac{50}{100}\right) \times \left(1 - \frac{25}{100}\right) = \frac{3}{8}$.

For the fourth example, Xiao Han first has a $\frac{50}{100}$ probability of defeating the first boss. After successfully defeating it, he has a $\frac{60}{100}$ probability of taking damage. Then, Xiao Han reaches a rest point and his health is fully restored regardless of whether he took damage or not. Then there is another $\frac{50}{100}$ probability of defeating the second boss. Thus, the probability of clearing is $\frac{50}{100} \times \frac{50}{100} = \frac{1}{4}$.