Description

派大星有 $n$ 个儿子，编号从 $1$ 到 $n$。

它现在想把 $C$ 个糖果分给它的儿子们，当然每个儿子分到的糖果都必须是非负整数。

若第 $i$ 个儿子分配到了 $a_i$ 个糖果：

• 设第 $i$ 个儿子的一颗赛艇度为 $X_i$。

• 则第 $i$ 个儿子的愉悦值为 $x_i^{a_i}$。

一种分配方案的愉悦度为该分配方案下，所有儿子的愉悦度的 乘积（$\prod_{i=1}^nx_i^{a_i}$）。

我们定义当第 $i$ 个儿子的一颗赛艇度为 $x_i$ 时，所有分配方案 的愉悦度的 和 为 $f(x_1, x_2, ... x_n)$。

现在第 $i$ 个儿子的一颗赛艇度 $x_i$ 可能是 $[l_i, r_i]$ 中的一个值。

派大星想求所有可能的一颗赛艇度情况下，$f(x_1,x_2, ... x_n)$ 的和（对 $10^9 + 7$ 取模）。

即 $\sum_{x_1 = l_1}^{r_1} \sum_{x_2 = l_2}^{r_2} ... \sum_{x_n = l_n}^{r_n}f(x_1, x_2, ... x_n)$。

Input Format

从 candies.in 读入数据。

n c

l1 l2 ... ln

r1 r2 ... rn

Output Format

向 candies.out 输出数据。

输出 $\sum_{x_1 = l_1}^{r_1} \sum_{x_2 = l_2}^{r_2} ... \sum_{x_n = l_n}^{r_n}f(x_1, x_2, ... x_n)$ $mod 10^9 + 7$。

Sample

样例输入1

2 3
1 1
1 1

样例输出1

4

样例1解释

这个例子中，$x_1 = x_2 = 1$，答案即为 $f(1, 1)$。

分配方案有四种：

• $a_1 = 0, a_2 = 3$： $1^0 * 1^3 = 1$。
• $a_1 = 1, a_2 = 2$： $1^1 * 1^2 = 1$。
• $a_1 = 2, a_2 = 1$： $1^2 * 1^1 = 1$。
• $a_1 = 3, a_2 = 0$： $1^3 * 1^0 = 1$。

所以 $f(1, 1) = 1 + 1 + 1 + 1 = 4$ 。

样例输入2

1 2
1
3

样例输出2

14

样例2解释

这个例子中，只有一个儿子， $x_i$ 从 $1$ ~ $3$ ，糖果 $2$ 个只能全部给它。

答案为 $f(1) + f(2) + f(3)$。

其中 $f(1) = 1^2$，$f(2) = 2^2$，$f(3) = 3^2$，所以答案是 $1 + 4 + 9 = 14$。

Hint

| part | $n$ | $c$ | $l_i$,$r_i$ |

| ------ | ----------------- | ----------------- | --------------------------- |

| $20\%$ | $1 \le n \le 2$ | | $l_i = r_i$ |

| $50\%$ | | | $l_i = r_i$ |

| $all$ | $1 \le n \le 400$ | $1 \le c \le 400$ | $1 \le l_i \le r_i \le 400$ |