P10066 [CCO 2023] Binaria

You have been hired by the Cheap Communication Organization (CCO) to research a breakthrough communication technology: Submessage Sums (SMS). The revolutionary idea is as follows. Given a binary string of length $N$ and a positive integer $K$ with $K \leq N$, the SMS of the string consists of $N-K+1$ integers. The first number in the sequence is the sum of the first $K$ bits, the second number is the sum of bits $2$ through $K+1$, and so on. The last number is the sum of bits $N-K+1$ through $N$. For example, if $K=4$, then the SMS of the binary string $110010$ is $2,2,1$. This is because $1+1+0+0=2$, $1+0+0+1=2$, and $0+0+1+0=1$. Since you are a beginner, your job is not to find the original binary string from a given SMS, but to find the number of binary strings that could produce this SMS.

The first line contains two integers $N$ and $K$, separated by spaces. The second line contains $N-K+1$ integers separated by spaces. It is guaranteed that this sequence is the SMS of at least one binary string.

Output $T \bmod (10^{6}+3)$, where $T$ is the positive integer equal to the total number of binary strings that correspond to the given SMS.

Possible strings of length $7$ are $1011001$, $1101010$, and $1110011$. For all testdata, $1 \leq N \leq 10^6$ and $1 \leq K \leq N$. | Subtask ID | Score | Range of $N$ | Range of $K$ | | :-: | :-: | :-: | :-: | | 1 | 12 | $1 \leq N \leq 10$ | $K \leq 3$ | | 2 | 12 | $1 \leq N \leq 10$ | None | | 3 | 16 | $1 \leq N \leq 1000$ | $K \leq 10$ | | 4 | 16 | $1 \leq N \leq 10^{6}$ | $K \leq 20$ | | 5 | 16 | $1 \leq N \leq 10^{6}$ | $K \leq 3000$ | | 6 | 28 | $1 \leq N \leq 10^{6}$ | None | Translated by ChatGPT 5