盒子与球

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

有 $n$ 个盒子排成一行，编号从 $1$ 到 $n$。有些盒子里有一个球，其余盒子是空的。至少有一个盒子里有球，至少有一个盒子是空的。

每次操作，你必须选择一个有球的盒子和一个相邻的空盒子，并将球从一个盒子移动到另一个盒子。对于所有 $i$ 从 $1$ 到 $n-1$，盒子 $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 —— 从前两种排列中的任意一个在第一次操作后得到。

数据范围

对于所有数据，$2\le n\le1500$，$1\le k\le1500$，$a_i\in\{0,1\}$，且序列中至少有一个 $0$ 和一个 $1$。

每个测试点独立计分。