问题陈述

12:17 (UTC): 样例输入1和2被交换了。错误已经修复。非常抱歉给您带来的不便。

AtCoder幼儿园里有N个孩子，方便地编号为1到N。Evi先生将发给孩子们C个无法区分的糖果。

如果孩子i得到a个糖果，孩子的快乐程度将变为xi的幂次方，其中xi是孩子的兴奋等级。幼儿园的活动水平是所有N个孩子的快乐程度的乘积。

对于通过给每个孩子零个或多个糖果来将C个糖果分配给孩子的每种可能方式，计算幼儿园的活动水平。然后，计算分配C个糖果的所有可能方式的总和。这个总和可以看作是孩子们的兴奋水平x1,..,xN的函数，因此我们称之为f(x1,..,xN)。

给定整数Ai,Bi (1≦i≦N)。找到模$10^9+7$。

约束条件

• $1≦N≦400$
• $1≦C≦400$
• $1≦Ai≦Bi≦400 (1≦i≦N)$

部分分数

• 通过满足$Ai=Bi (1≦i≦n)$的测试集将获得400分。

---

输入

输入以以下格式从标准输入给出：

$N$ $C$ $A_1$ $A_2$ ... $A_N$ $B_1$ $B_2$ ... $B_N$

输出

打印模$10^9+7$的值。

---

样例输入1

2 3
1 1
1 1

样例输出1

4

这个例子包含在部分得分的测试集中，因为$Ai=Bi$。我们只需要考虑幼儿园活动水平的总和，其中孩子1和孩子2的兴奋水平都是1 ($f(1,1)$)。

• 如果孩子1没有糖果，孩子2获得3个糖果，幼儿园的活动水平为$1^0\*1^3=1$。
• 如果孩子1获得1个糖果，孩子2获得2个糖果，幼儿园的活动水平为$1^1\*1^2=1$。
• 如果孩子1获得2个糖果，孩子2获得1个糖果，幼儿园的活动水平为$1^2\*1^1=1$。
• 如果孩子1获得3个糖果，孩子2没有糖果，幼儿园的活动水平为$1^3\*1^0=1$。

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

---

样例输入2

1 2
1
3

样例输出2

14

由于只有一个孩子，孩子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$。

---

样例输入3

2 3
1 1
2 2

样例输出3

66

由于可以看出$f(1,1)=4 , f(1,2)=15 , f(2,1)=15 , f(2,2)=32$，所以答案是$4+15+15+32=66$。

---

样例输入4

4 8
3 1 4 1
3 1 4 1

样例输出4

421749

这个例子包含在部分得分的测试集中。

---

样例输入5

3 100
7 6 5
9 9 9

样例输出5

139123417