题目背景

小蔡和小僖在比赛剪窗花。

题目描述

小蔡和小僖的制作水平都很高，换句话讲，他们都能制作出好看度为 $1\dots n$ 的窗花，但是两个人的熟练度不一样，小蔡的熟练度可以用一个数组 $a_{1\dots n}$ 组成，换句话讲，他剪出一个好看度为 $k(1\le k\le n)$ 的窗花的概率为 $\frac{a_k}{\sum_{i=1}^na_i}$。同理，小僖的熟练度可以用数组 $b_{1\dots n}$ 组成，他剪出一个好看度为 $k(1\le k\le n)$ 的窗花的概率为 $\frac{b_k}{\sum_{i=1}^nb_i}$。

现在两个人正在比赛剪窗花，如果某个人剪出的窗花的好看度比另一个人的大，那么这个人取胜，如果比另一个人的小，那么这个人失败，如果一样，则为平局。

现在，小蔡用一个计数器记录他的情况，如果他赢了，那么计数器 $+1$，如果他输了，那么计数器 $-1$，如果平了，那么不加不减。但由于计数器不支持负数，所以如果结果 $\le0$ 那么会自动变成 $0$，如果计数器显示的数 $=m$，那么比赛结束。

作为新时代的大神，小蔡花了 $10^{-6}$ 秒就算出来了比赛结束所经过的期望局数，但他想让你帮忙检验一下……

输入格式

第一行输入两个整数 $n, m$，详细见题目。
第二行输入 $n$ 个整数 $a_i$，表示第一个人的熟练度。
第三行输入 $n$ 个整数 $b_i$，表示第二个人的熟练度。

输出格式

一个整数，表示答案对 $10^9 + 7$ 取模之后的结果。

4 2
3 1 1 4 
3 5 2 1 

570934265

3 1
1 1 1
1 1 1

3

提示

对于 $30\%$ 的数据点，$1 \leq m \leq 100$。

对于 $60\%$ 的数据点，$1 \leq m \leq 10^{6}$。

对于 $90\%$ 的数据点，$1 \leq m \leq 10^{18}$。

对于 $100\%$ 的数据点，$2 \leq n \leq 10^6$，$1 \leq m \leq 10^{1000}$，$1 \leq a_i \leq 10^9$。