← 返回题目列表

Codeforces · 1845/E

E. 盒子和球

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

有 $$$n$$$ 个盒子排成一行。这些盒子的编号从 $$$1$$$ 到 $$$n$$$。有些盒子里面有一个球,其余的都是空的。至少一个盒子包含一个球并且至少一个盒子是空的。

在一步操作中,您必须选择一个里面有球的盒子和相邻的空盒子,然后将球从一个盒子移到另一个盒子中。从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$ 的框 $$$i$$$ 和 $$$i+1$$$ 被视为彼此相邻。框 $$$1$$$ 和 $$$n$$$ 不相邻。

在执行 $$$k$$$ 步之后,存在多少种不同的球排列?如果至少有一个这样的盒子,其中一个盒子中包含球,而另一个盒子中不包含球,则两种布置被认为是不同的。

由于答案可能相当大,因此打印其对 $$$10^9+7$$$ 取模的余数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 1500$$$; $$$1 \le k \le 1500$$$) — 盒子的数量和移动的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \in \{0, 1\}$$$) - $$$0$$$ 表示一个空盒子,$$$1$$$ 表示一个里面有球的盒子。至少有一个 $$$0$$$ 和至少一个 $$$1$$$。

输出

打印一个整数 - 在执行 $$$k$$$ 步之后可以存在的不同球排列的数量,以 $$$10^9+7$$$ 为模。

示例

输入 #1

4 1
1 0 1 0

输出 #1

3

输入 #2

4 2
1 0 1 0

输出 #2

2

输入 #3

10 6
1 0 0 1 0 0 0 1 1 1

输出 #3

69

注意

在第一个示例中,有以下可能的安排:

- 0 1 1 0 — 将球从 $$$1$$$ 框移动到 $$$2$$$ 框后获得;
- 1 0 0 1 — 将球从 $$$3$$$ 框移动到 $$$4$$$ 框后获得;
- 1 1 0 0 — 将球从 $$$3$$$ 框移动到 $$$2$$$ 框后获得。

在第二个示例中,有以下可能的安排:

- 1 0 1 0 — 三种获得方法:只需反转第一次移动期间执行的操作;
- 0 1 0 1 - 从第一步后的前两个排列中的任何一个获得。