{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $1≦N≦400$\n*   $1≦C≦400$\n*   $1≦A_i≦B_i≦400 (1≦i≦N)$"},{"iden":"partial score","content":"*   $400$ points will be awarded for passing the test set satisfying $A_i=B_i (1≦i≦N)$."},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"2 3\n1 1\n1 1"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"1 2\n1\n3"},{"iden":"sample output 2","content":"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$."},{"iden":"sample input 3","content":"2 3\n1 1\n2 2"},{"iden":"sample output 3","content":"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$."},{"iden":"sample input 4","content":"4 8\n3 1 4 1\n3 1 4 1"},{"iden":"sample output 4","content":"421749\n\nThis case is included in the test set for the partial score."},{"iden":"sample input 5","content":"3 100\n7 6 5\n9 9 9"},{"iden":"sample output 5","content":"139123417"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}