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 $ .

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 $ .

Print a single integer — the number of different arrangements of balls that can exist after exactly $ k $ moves are performed, modulo $ 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.