题目描述

AtCoder幼儿园里有N个小朋友，编号1~N，Evi先生要把C颗糖果分给他们。

小朋友可以得到任意多颗糖果，如果第$i$个小朋友，得到了$a$颗糖，他会得到$x_i^a$的愉悦度，$x_i$是第$i$个小朋友的兴奋度。幼儿园活跃指数定义为$N$个小朋友愉悦度的乘积。

令$f(x_1,x_2,...,x_N)$表示所有分糖果的方案对应的幼儿园活跃指数的和。

现在给出$A_i,B_i(1<=i<=N)$，要求 $\sum_{x_1=A_1}^{B_1} \sum_{x_2=A_2}^{B_2} ... \sum_{x_N=A_N}^{B_N} f(x_1,x_2,...,x_N)$，对1000000007取模。

输入格式

N，C

$A_1,A_2,...,A_N$

$B_1,B_2,...,B_N$

输出格式

一行一个整数表示答案

翻译提供者：XHRlyb_2001