Canadian Computing Olympiad: 2023 Day 1, Problem 1

You have been hired by the Cheap Communication Organization (CCO) to work on a communication breakthrough: sub-message sum (SMS). This revolutionary idea works as follows.

Given a binary string of length $N$, and some positive integer $K$ with $K\le N$, the SMS for the string consists of a sequence of $N-K+1$ sums. The first sum in the sequence is the sum of digits $1$ through $K$, the second sum is the sum of digits $2$ through $K+1$, and so on until the last sum which is the sum of digits $N-K+1$ through $N$.

For example, if $K=4$, 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 very junior developer, your job is not to find the original binary string from a given SMS, but rather the number of binary strings that could have formed this SMS.

Input Specification

The first line of input contains the two space-separated integers $N$ and $K$ where $1\le K\le N$. The second line of input contains $N-K+1$ space-separated integers which is the SMS of at least one binary string.

Marks Awarded	Bounds on $N$	Additional Bounds on $K$
$3$ marks	$1\le N\le 10$	$K\le 3$
$3$ marks	$1\le N\le 10$	None
$4$ marks	$1\le N\le 1000$	$K\le 10$
$4$ marks	$1\le N\le {10}^6$	$K\le 20$
$4$ marks	$1\le N\le {10}^6$	$K\le 3000$
$7$ marks	$1\le N\le {10}^6$	None

Output Specification

Output the remainder of $T$ divided by the prime number ${10}^6+3$ where $T$ is the positive integer equal to the total number of possible binary strings that correspond to the given SMS.

Sample Input

7 4
3 2 2 2

Output for Sample Input

3

Explanation of Output for Sample Input

The possible strings of length $7$ are 1011001, 1101010, and 1110011.