Problem Description

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.

Input Format

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 Format

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.

7 4
3 2 2 2

3

Hint

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

Translated by ChatGPT 5