分数: 800 点
问题陈述
12:17 (UTC):示例输入 1 和 2 已交换。该错误现已修复。对于给您带来的不便,我们深表歉意。
有 N AtCoder 幼儿园的孩子们,编号方便 1 通过 N。 Evi先生将分发 C 给孩子们的糖果难以区分。
如果孩子 给出 i 被给予 a 糖果,孩子的 幸福 将变成 x_i^a,其中 x_i 是孩子的 兴奋程度。的 活动水平 幼儿园的 是 产品 所有人的幸福 N 孩子们。
对于每种可能的分发方式 C 给孩子们糖果 通过给每个孩子零个或更多糖果,计算幼儿园的活动水平。然后,计算所有可能的分配方式的总和 C 糖果。这个总和可以看作是孩子们兴奋程度的函数 x_1,..,x_N,因此我们称之为 f(x_1,..,x_N).
给你整数 A_i,B_i (1≦i≦N)。查找
模数 10^9+7.
约束
- 1≦N≦400
- 1≦C≦400
- 1≦A_i≦B_i≦400 (1≦i≦N)
部分分数
- 400 通过满足以下条件的测试集将获得积分 A_i=B_i (1≦i≦N).
输入
输入由标准输入按以下格式给出:
N C A_1 A_2 ... A_N B_1 B_2 ... B_N
输出
打印以下值
模数 10^9+7.
示例输入 1
2 3 1 1 1 1
示例输出 1
4
这种情况包含在部分分数的测试集中,因为 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.
示例输入 2
1 2 1 3
示例输出 2
14
由于只有一个孩子,孩子 1的幸福感本身就是幼儿园的活动水平。由于唯一可能的分配方式 2 糖果是给孩子两颗糖果 1,这种情况下的活动级别将变为以下值 f.
- 当孩子的兴奋程度 1 is 1, f(1)=1^2=1.
- 当孩子的兴奋程度 1 is 2, f(2)=2^2=4.
- 当孩子的兴奋程度 1 is 3, f(3)=3^2=9.
因此,答案是 1+4+9=14.
示例输入 3
2 3 1 1 2 2
示例输出 3
66
既然可以看出 f(1,1)=4 , f(1,2)=15 , f(2,1)=15 , f(2,2)=32,答案是 4+15+15+32=66.
示例输入 4
4 8 3 1 4 1 3 1 4 1
示例输出 4
421749
此案例包含在部分分数的测试集中。
示例输入 5
3 100 7 6 5 9 9 9
示例输出 5
139123417