← 返回题目列表

AtCoder · arc059_c

E. 儿童和糖果

中文机器翻译题面 查看原题

分数: 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