You have been hired by a low-cost communication organization to research a breakthrough communication technology: Sub-Message Sums (SMS). This revolutionary idea is as follows.

Given a binary string of length $N$ and a positive integer $K$ such that $K \le N$, the SMS of this 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 the bits from the 2nd to the $(K+1)$-th position, and so on, with the last number being the sum of the bits from the $(N-K+1)$-th to the $N$-th position.

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 novice, your job is not to find the original binary string from the given SMS, but to find the number of binary strings that could form this SMS.

Input

The first line contains two space-separated integers $N$ and $K$.

The second line contains $N - K + 1$ space-separated integers, guaranteed to be the SMS of at least one binary string.

Output

Output the result modulo $10^6 + 3$, where $T$ is the total number of binary strings corresponding to the given SMS.

Examples

Input 1

7 4
3 2 2 2

Output 1

3

Note 1

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

Constraints

For all data, $1 \le N \le 10^6$, $1 \le K \le N$.

Subtasks