现在有 $n$ 个小朋友，编号从 $1$ 到 $n$，每个小朋友有一个赛艇度 $x_i$。老师手上有 $c$ 颗糖果，准备全部分给小朋友们，每个小朋友分到的糖果数应当是非负整数。
假设第 $i$ 个小朋友分到 $a_i$ 个糖果，那么第 $i$ 个小朋友的愉悦度为 $x_i^{a_i}$。定义一种分配方案的愉悦度为，这种分配方案下所有小朋友愉悦度的乘积，即
$$\prod_{i=1}^{n}x_i^{a_i}$$
我们定义 $f(x_1,x_2,\ldots,x_n)$ 表示现在有 $n$ 个小朋友，编号从 $1$ 到 $n$，第 $i$ 个小朋友有一个赛艇度 $x_i$ 时，所有分配方案的愉悦度之和。
现在，给定每个小朋友的赛艇度区间 ，求
$$\sum_{x_{1}=l_{1}}^{r_{1}} \sum_{x_{2}=l_{2}}^{r_{2}} \ldots \sum_{x_{n}=l_{n}}^{r_{n}} f\left(x_{1}, x_{2}, \ldots, x_{n}\right)$$
输出答案对  取模的结果即可。

第一行包含两个正整数 $n,c$。
第二行包含 $n$ 个正整数，第 $i$ 个数表示 $l_i$。
第三行包含 $n$ 个正整数，第 $i$ 个数表示 $r_i$。

输出一行一个整数表示答案，对 $10^9+7$ 取模。

2 3
1 1
1 1

4

1 2
1
3

14

3 100
7 6 5
9 9 9

139123417