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

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$ 取模。

无

无

### 制約 - $ 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 部分点の条件を満たします。