Background

Xiao Cai and Xiao Xi are competing in cutting window decorations.

Problem Description

Both Xiao Cai and Xiao Xi are very skilled. In other words, each of them can make window cuttings with beauty values from $1 \dots n$. However, their proficiency is different.

Xiao Cai's proficiency can be represented by an array $a_{1 \dots n}$. That is, the probability that he cuts a window cutting with beauty value $k \ (1 \le k \le n)$ is $\frac{a_k}{\sum_{i=1}^n a_i}$. Similarly, Xiao Xi's proficiency can be represented by an array $b_{1 \dots n}$, and the probability that he cuts a window cutting with beauty value $k \ (1 \le k \le n)$ is $\frac{b_k}{\sum_{i=1}^n b_i}$.

Now the two are competing. If one person's window cutting has a higher beauty value than the other's, that person wins. If it is lower, that person loses. If they are equal, it is a draw.

Xiao Cai uses a counter to record his status: if he wins, the counter is $+1$; if he loses, the counter is $-1$; if it is a draw, the counter does not change. However, because the counter does not support negative numbers, if the result is $\le 0$ it will automatically become $0$. If the number shown on the counter is $= m$, then the competition ends.

As a top expert of the new era, Xiao Cai computed in $10^{-6}$ seconds the expected number of rounds until the competition ends, but he wants you to help verify it.

Input Format

The first line contains two integers $n, m$, as described in the statement.
The second line contains $n$ integers $a_i$, representing the proficiency of the first person.
The third line contains $n$ integers $b_i$, representing the proficiency of the second person.

Output Format

Output one integer, which is the answer modulo $10^9 + 7$.

4 2
3 1 1 4 
3 5 2 1 

570934265

3 1
1 1 1
1 1 1

3

Hint

For $30\%$ of the testdata, $1 \le m \le 100$.

For $60\%$ of the testdata, $1 \le m \le 10^{6}$.

For $90\%$ of the testdata, $1 \le m \le 10^{18}$.

For $100\%$ of the testdata, $2 \le n \le 10^6$, $1 \le m \le 10^{1000}$, $1 \le a_i \le 10^9$.

Translated by ChatGPT 5