CF1845E.Boxes and Balls

There are $n$ boxes placed in a line. The boxes are numbered from $1$ to $n$. Some boxes contain one ball inside of them, the rest are empty. At least one box contains a ball and at least one box is empty.

In one move, you have to choose a box with a ball inside and an adjacent empty box and move the ball from one box into another. Boxes $i$ and $i+1$ for all $i$ from $1$ to $n-1$ are considered adjacent to each other. Boxes $1$ and $n$ are not adjacent.

How many different arrangements of balls exist after exactly $k$ moves are performed? Two arrangements are considered different if there is at least one such box that it contains a ball in one of them and doesn't contain a ball in the other one.

Since the answer might be pretty large, print its remainder modulo $10^9+7$.

有 $n$ 个盒子排成一行，编号从 $1$ 到 $n$。其中一些盒子中各含一个球，其余盒子为空。至少有一个盒子含球，且至少有一个盒子为空。

一次操作定义为：选择一个含球的盒子和一个与其相邻的空盒子，并将该球从含球盒子移动到空盒子中。对于所有 $i$（$1 \le i \le n-1$），盒子 $i$ 与盒子 $i+1$ 被视为彼此相邻；而盒子 $1$ 与盒子 $n$ 不相邻。

恰好执行 $k$ 次操作后，共能形成多少种不同的球分布方案？若存在至少一个盒子，在两种方案中一个含球、另一个不含球，则称这两种方案不同。

由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

The first line contains two integers $n$ and $k$ ($2 \le n \le 1500$; $1 \le k \le 1500$) — the number of boxes and the number of moves.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($a_i \in {0, 1}$) — $0$ denotes an empty box and $1$ denotes a box with a ball inside. There is at least one $0$ and at least one $1$.

第一行包含两个整数 $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$。

Print a single integer — the number of different arrangements of balls that can exist after exactly $k$ moves are performed, modulo $10^9+7$.

输出一个整数——恰好执行 $k$ 次移动后，球可能存在的不同排列方式的数量，对 $10^9+7$ 取模。

In the first example, there are the following possible arrangements:

• 0 1 1 0 — obtained after moving the ball from box $1$ to box $2$;
• 1 0 0 1 — obtained after moving the ball from box $3$ to box $4$;
• 1 1 0 0 — obtained after moving the ball from box $3$ to box $2$.

In the second example, there are the following possible arrangements:

• 1 0 1 0 — three ways to obtain that: just reverse the operation performed during the first move;
• 0 1 0 1 — obtained from either of the first two arrangements after the first move.

在第一个例子中，存在以下可能的排列：

• 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 — 由第一次操作后的前两种排列之一得到。