题目描述

译自 CCO 2023 Day1 T1「Binaria」。

你被廉价通信组织（CCO）雇佣来研究一项突破性的通信技术：子消息和（SMS）。这个革命性的想法如下：

给定一个长度为 $N$ 的二进制字符串（仅由 $\texttt{0}$ 和 $\texttt{1}$ 组成）和一个满足 $K \leq N$ 的正整数 $K$，该字符串的 SMS 由 $N-K+1$ 个整数组成。序列中的第一个数是前 $K$ 位的和，第二个数是第 $2$ 位到第 $K+1$ 位的和，依此类推，最后一个数是第 $N-K+1$ 位到第 $N$ 位的和。

例如，如果 $K=4$，二进制字符串 $\texttt{110010}$（长度 $N=6$）的 SMS 是 $2,2,1$。这是因为：

• 前 $4$ 位：$\texttt{1+1+0+0}=2$；
• 第 $2 \sim 5$ 位：$\texttt{1+0+0+1}=2$；
• 第 $3 \sim 6$ 位：$\texttt{0+0+1+0}=1$。

你的工作是：给定一个 SMS 序列，计算可能形成该 SMS 的二进制字符串的数量 $T$。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $K$，分别表示二进制字符串的长度和 SMS 的窗口大小。

第二行包含 $M = N-K+1$ 个用空格分隔的整数（记为 $s_1, s_2, \ldots, s_M$），保证该序列至少对应一个二进制字符串的 SMS。

输出格式

输出 $T$ 对 $10^6+3$ 取模的结果，其中 $T$ 是可能的二进制字符串的总数。

样例

输入

7 4
3 2 2 2

输出

3

样例解释

长度为 $7$ 的可能二进制字符串有 $\texttt{1011001}$、$\texttt{1101010}$ 和 $\texttt{1110011}$，共 $3$ 种，因此输出 $3$。

数据范围与提示

对于所有的数据，有 $1 \leq N \leq 10^6$，$1 \leq K \leq N$。

详细子任务附加限制及分值如下表所示：