Given an integer sequence of length $$$n$$$, $$$b_1, b_2, \dots b_n$$$, and a magic parameter integer $$$k$$$. To perform one magic operation, you need to select a positive integer $$$x$$$ such that $$$k \le x \le n - k$$$, set the integer $$$t = b_{x + 1} - b_x$$$, and then perform the following operations:
Now you need to determine how many different sequences $$$b_1, b_2, \dots b_n$$$ can be obtained after performing any number of magic operations (including $$$0$$$ operations). Since the answer may be large, you only need to output the result modulo $$$10^9 + 7$$$.
It can be proven that there are only a finite number of possible sequences $$$b$$$. Two sequences $$$S$$$ and $$$T$$$ are considered different if there exists some position $$$z$$$ such that $$$S_z \ne T_z$$$.
The first line contains two positive integers $$$n$$$ and $$$k$$$, representing the length of the sequence and the magic parameter.
The second line contains $$$n$$$ positive integers $$$b_1, b_2, \dots b_n$$$, representing the initially given integer sequence.
$$$2 \le n \le 5 \times 10^5$$$, $$$1 \le k \le \left\lfloor\dfrac{n}{2}\right\rfloor$$$, $$$-10^9 \le b_i \le 10^9$$$
Only one integer, representing the number of different sequences $$$b$$$ that can be obtained, output modulo $$$10^9 + 7$$$.
4 1 -1 -1 0 3
12
10 2 1 -6 -2 3 -1 -1 -1 -6 2 5
120
