28317번 - Binaria 다국어

문제

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.

입력

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.

출력

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.

제한

• 1ドル \le N \le 10^6$

힌트