{"problem":{"name":"[CCO 2023] Binaria","description":{"content":"你被廉价通信组织（CCO）雇佣来研究一项突破性的通信技术：子消息和（SMS）。这个革命性的想法是这样的。 给定一个长度为 $N$ 的二进制字符串和一个满足 $K \\leq N$ 的正整数 $K$，该字符串的 SMS 由 $N-K+1$ 个整数组成。序列中的第一个数是前 $K$ 位的和，第二个数是第 $2$ 位到第 $K+1$ 位的和，依此类推，最后一个数是第 $N-K+1$ 位到第 $N$ 位的","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10066"},"statements":[{"statement_type":"Markdown","content":"你被廉价通信组织（CCO）雇佣来研究一项突破性的通信技术：子消息和（SMS）。这个革命性的想法是这样的。\n\n给定一个长度为 $N$ 的二进制字符串和一个满足 $K \\leq N$ 的正整数 $K$，该字符串的 SMS 由 $N-K+1$ 个整数组成。序列中的第一个数是前 $K$ 位的和，第二个数是第 $2$ 位到第 $K+1$ 位的和，依此类推，最后一个数是第 $N-K+1$ 位到第 $N$ 位的和。\n\n例如，如果 $K=4$，那么二进制字符串 $110010$ 的 SMS 是 $2,2,1$。这是因为 $1+1+0+0=2,1+0+0+1=2$，以及 $0+0+1+0=1$。\n\n由于你是一个新手，你的工作不是从给定的 SMS 中找到原始的二进制字符串，而是找到可能形成这个 SMS 的二进制字符串的数量。\n\n## Input\n\n第一行包含两个用空格分隔的整数 $N$ 和 $K$。\n\n第二行包含 $N-K+1$ 个用空格分隔的整数，保证它至少是一个二进制字符串的 SMS。\n\n## Output\n\n输出 $T$ 对 $10^{6}+3$ 取模的结果，其中 $T$ 是等于与给定 SMS 对应的可能的二进制字符串的总数的正整数。\n\n[samples]\n\n## Note\n\n长度为 $7$ 的可能的字符串有 $1011001$，$1101010$ 和 $1110011$。\n\n对于所有的数据，有 $1\\leq N\\leq 10^6$，$1 \\leq K \\leq N$。\n\n| 子任务编号 |\t分值\t| $N$ 的范围\t| $K$ 的范围 |\n| :-: |  :-: |  :-: |  :-: |\n|1\t|12\t|$1 \\leq N \\leq 10$|\t$K \\leq 3$|\n|2\t|12\t| $1 \\leq N \\leq 10$|无 |\n|3\t|16\t|$1 \\leq N \\leq 1000$\t|$K \\leq 10$|\n|4\t|16\t|$1 \\leq N \\leq 10^{6}$|\t$K \\leq 20$|\n|5\t|16\t| $1 \\leq N \\leq 10^{6}$| $K\\leq 3000$|\n|6\t|28\t|$1 \\leq N \\leq 10^{6}$|无|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10066","tags":["2023","CCO（加拿大）","图论建模"],"sample_group":[["7 4\n3 2 2 2","3"]],"created_at":"2026-03-03 11:09:25"}}