配点 : $800$ 点

問題文

競プロ幼稚園には$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 \leq i \leq N)$が与えられるので、

を$10^9+7$で割ったあまりを求めてください。

制約

• $1 \leq N \leq 400$
• $1 \leq C \leq 400$
• $1 \leq A_i \leq B_i \leq 400 (1 \leq i \leq N)$

部分点

• $A_i=B_i (1 \leq i \leq N)$ を満たすデータセットに正解した場合は、部分点として$400$ 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $C$

$A_1$ $A_2$ ... $A_N$

$B_1$ $B_2$ ... $B_N$

出力

の値を$10^9+7$で割ったあまりを出力せよ。

2 3
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$です。

1 2
1
3

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$となります。

2 3
1 1
2 2

66

$f(1,1)=4 , f(1,2)=15 , f(2,1)=15 , f(2,2)=32$ となることがわかるので、答えは$4+15+15+32=66$になります。

4 8
3 1 4 1
3 1 4 1

421749

部分点の条件を満たします。

3 100
7 6 5
9 9 9

139123417