CF1845E Boxes and Balls

有 $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$ 取模。

在第一个样例中，可能的排列有： - 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 —— 从前两种排列中的任意一个在第一次操作后得到。 由 ChatGPT 4.1 翻译