{"problem":{"name":"Children and Candies","description":{"content":"**12:17 (UTC): The sample input 1 and 2 were swapped. The error is now fixed. We are very sorry for your inconvenience.** There are $N$ children in AtCoder Kindergarten, conveniently numbered $1$ thro","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc059_c"},"statements":[{"statement_type":"Markdown","content":"**12:17 (UTC): The sample input 1 and 2 were swapped. The error is now fixed. We are very sorry for your inconvenience.**\nThere are $N$ children in AtCoder Kindergarten, conveniently numbered $1$ through $N$. Mr. Evi will distribute $C$ indistinguishable candies to the children.\nIf child $i$ is given $a$ candies, the child's _happiness_ will become $x_i^a$, where $x_i$ is the child's _excitement level_. The _activity level_ of the kindergarten is the **product** of the happiness of all the $N$ children.\nFor each possible way to distribute $C$ candies to the children by giving zero or more candies to each child, calculate the activity level of the kindergarten. Then, calculate the sum over all possible way to distribute $C$ candies. This sum can be seen as a function of the children's excitement levels $x_1,..,x_N$, thus we call it $f(x_1,..,x_N)$.\nYou are given integers $A_i,B_i (1≦i≦N)$. Find ![image](http://arc059.contest.atcoder.jp/img/arc/059/E_sigmaf.gif) modulo $10^9+7$.\n\n## Constraints\n\n*   $1≦N≦400$\n*   $1≦C≦400$\n*   $1≦A_i≦B_i≦400 (1≦i≦N)$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $C$\n$A_1$ $A_2$ ... $A_N$\n$B_1$ $B_2$ ... $B_N$\n\n## Partial Score\n\n*   $400$ points will be awarded for passing the test set satisfying $A_i=B_i (1≦i≦N)$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc059_c","tags":[],"sample_group":[["2 3\n1 1\n1 1","4\n\nThis case is included in the test set for the partial score, since $A_i=B_i$. We only have to consider the sum of the activity level of the kindergarten where the excitement level of both child $1$ and child $2$ are $1$ ($f(1,1)$).\n\n*   If child $1$ is given $0$ candy, and child $2$ is given $3$ candies, the activity level of the kindergarten is $1^0*1^3=1$.\n*   If child $1$ is given $1$ candy, and child $2$ is given $2$ candies, the activity level of the kindergarten is $1^1*1^2=1$.\n*   If child $1$ is given $2$ candies, and child $2$ is given $1$ candy, the activity level of the kindergarten is $1^2*1^1=1$.\n*   If child $1$ is given $3$ candies, and child $2$ is given $0$ candy, the activity level of the kindergarten is $1^3*1^0=1$.\n\nThus, $f(1,1)=1+1+1+1=4$, and the sum over all $f$ is also $4$."],["1 2\n1\n3","14\n\nSince there is only one child, child $1$'s happiness itself will be the activity level of the kindergarten. Since the only possible way to distribute $2$ candies is to give both candies to child $1$, the activity level in this case will become the value of $f$.\n\n*   When the excitement level of child $1$ is $1$, $f(1)=1^2=1$.\n*   When the excitement level of child $1$ is $2$, $f(2)=2^2=4$.\n*   When the excitement level of child $1$ is $3$, $f(3)=3^2=9$.\n\nThus, the answer is $1+4+9=14$."],["2 3\n1 1\n2 2","66\n\nSince it can be seen that $f(1,1)=4 , f(1,2)=15 , f(2,1)=15 , f(2,2)=32$, the answer is $4+15+15+32=66$."],["4 8\n3 1 4 1\n3 1 4 1","421749\n\nThis case is included in the test set for the partial score."],["3 100\n7 6 5\n9 9 9","139123417"]],"created_at":"2026-03-03 11:01:14"}}