問題文

競プロ幼稚園には$1$～$N$の番号がついた$N$人の子供がいます。えび先生は、区別できない$C$個のキャンディーを子供たちに分配することにしました。子供$i$の_はしゃぎ度_が$x_i$の時、キャンディーを$a$個もらうと子供$i$の_うれしさ_は$x_i^a$になります。幼稚園の活発度_は$N$人の子供たちの_うれしさ_の積になります。各子供にキャンディーを非負整数個配ってC個配りきる方法それぞれに対して_幼稚園の活発度_を計算して、その総和を子供たちの_はしゃぎ度$x_1$,..,$x_N$の関数とみて$f(x_1,..,x_N)$とおきます。$A_i,B_i (1≦i≦N)$が与えられるので、 を$10^9+7$で割ったあまりを求めてください。

制約

• $1≦N≦400$
• $1≦C≦400$
• $1≦A_i≦B_i≦400 (1≦i≦N)$

部分点

• $A_i=B_i (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

$A_i=B_i$なので部分点の条件を満たします。 子供$1$,$2$の_はしゃぎ度_が共に$1$のもの($f(1,1)$)を考えればよく、この時、

• 子供$1$に$0$個,子供$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$に$0$個のキャンディーをあげると、_幼稚園の活発度_は$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$にあげる$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