AT_arc059_c [ARC059E] キャンディーとN人の子供

[problemUrl]: https://atcoder.jp/contests/arc059/tasks/arc059_c 競プロ幼稚園には$ 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 $で割ったあまりを求めてください。

N/A

N/A

### 制約 - $ 1≦N≦400 $ - $ 1≦C≦400 $ - $ 1≦A_i≦B_i≦400\ (1≦i≦N) $ ### 部分点 - $ A_i=B_i\ (1≦i≦N) $ を満たすデータセットに正解した場合は、部分点として$ 400 $ 点が与えられる。 ### Sample Explanation 1 $ 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 $です。 ### Sample Explanation 2 子供が一人なので、子供$ 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 $となります。 ### Sample Explanation 3 $ f(1,1)=4\ ,\ f(1,2)=15\ ,\ f(2,1)=15\ ,\ f(2,2)=32 $ となることがわかるので、答えは$ 4+15+15+32=66 $になります。 ### Sample Explanation 4 部分点の条件を満たします。