d1p1 — CCO Canadian_Computing_Olympiad
Task type: batch | Time limit: 1 s | Memory limit: 1024 MB | Difficulty: 17
Algorithms: number theory, ad-hoc, mathematics, combinatorics, modular arithmetic

# 2023 Canadian Computing Olympiad
# Day 1, Problem 1
# Binaria

### Time Limit: 1 second

## Problem Description

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
```

### Sample Output

```
3
```

#### Explanation of Output for Sample Input

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

Starter code: