题目描述

AtCoder 幼儿园里有 $N$ 个小朋友，编号 $1\sim N$，Evi 先生要把 $C$ 颗糖果分给他们。

小朋友可以得到任意多颗糖果。如果第 $i$ 个小朋友得到了 $a$ 颗糖，那么他会得到 $x_i^a$ 的愉悦度，其中 $x_i$ 是第 $i$ 个小朋友的兴奋度。幼儿园活跃指数定义为 $N$ 个小朋友愉悦度的乘积。

令 $f(x_1,x_2,\cdots,x_N)$ 表示所有分糖果的方案对应的幼儿园活跃指数的和。

现在给出 $A_i,B_i(1\le i\le N)$，求 $\sum\_{x\_1=A\_1}^{B\_1} \sum\_{x\_2=A\_2}^{B\_2} \cdots \sum\_{x\_N=A\_N}^{B\_N} f(x\_1,x\_2,...,x\_N)$，对 $10 ^ 9 + 7$ 取模。

输入格式

$N,C$

$A_1,A_2,\cdots,A_N$

$B_1,B_2,\cdots,B_N$

输出格式

一行一个整数表示答案。

样例 1

输入

2 3
1 1
1 1

输出

4

样例 2

输入

1 2
1
3

输出

14

样例 3

输入

2 3
1 1
2 2

输出

66

样例 4

输入

4 8
3 1 4 1
3 1 4 1

输出

421749

样例 5

输入

3 100
7 6 5
9 9 9

输出

139123417

说明/提示

样例解释

第一组测试样例满足 $A_i =B_i$ 的部分分设置要求。

我们只需要考虑当两个孩子的兴奋度都为 $1$ 时的幼儿园活动水平之和（即 $f(1,1)$）。

• 若第 $1$ 个孩子分得 $0$ 颗糖，第 $2$ 个孩子分得 $3$ 颗糖，则活动水平为 $1^0 \times 1^3 = 1$。
• 若第 $1$ 个孩子分得 $1$ 颗糖，第 $2$ 个孩子分得 $2$ 颗糖，则活动水平为 $1^1 \times 1^2 = 1$。
• 若第 $1$ 个孩子分得 $2$ 颗糖，第 $2$ 个孩子分得 $1$ 颗糖，则活动水平为 $1^2 \times 1^1 = 1$。
• 若第 $1$ 个孩子分得 $3$ 颗糖，第 $2$ 个孩子分得 $0$ 颗糖，则活动水平为 $1^3 \times 1^0 = 1$。

因此，$f(1,1) = 1 + 1 + 1 + 1 = 4$，并且所有 $f$ 的总和也是 $4$。

---

第二组测试样例，因为这里只有一个孩子，所以孩子 $1$ 的愉悦度本身就是幼儿园的活动水平。

由于分配 $2$ 颗糖果的唯一方式是将两颗糖都给孩子 $1$，因此该情况下的活动水平就是 $f$ 的值。

• 当孩子 $1$ 的愉悦度为 $1$ 时，$f(1)=1^2=1$。
• 当孩子 $1$ 的愉悦度为 $2$ 时，$f(2)=2^2=4$。
• 当孩子 $1$ 的愉悦度为 $3$ 时，$f(3)=3^2=9$。

因此，答案为 $1+4+9=14$。

---

对于第三组测试样例，有 $f(1,1)=4$，$f(1,2)=15$，$f(2,1)=15$，$f(2,2)=32$，因此答案为 $4+15+15+32=66$。

数据范围

对于 $50\%$ 的数据：$1 \le N,C \le 400$，$1\le A_i=B_i \le 400$。

对于 $100\%$ 的数据：$1 \le N,C \le 400$，$1\le A_i\le B_i \le 400$。

翻译提供者：XHRlyb_2001