串串(string)

题目描述

给你一个长度为 $n$ 的 $01$ 串 $S$，你可以进行任意次在 $S$ 任意位置插入或删除 $00$ 、$111$、$010101$ 中的任意一个串，有 $q$ 次询问，问你可以得到多少种不同的长度为 $m$ 的串。

输入格式

第一行两个正整数 $n$ 和 $q$。

第二行一个 $01$ 串 $S$。

接下来 $q$ 行每行一个正整数 $m$ 代表一次询问。

输出格式

对于每组询问，输出一行一个数，表示答案对 $10^9+9$ 取模后的结果。

输入输出样例 1

输入输出样例 2

说明/提示

对于全部的数据，$1\le n\le10^6$，$1 \le m \le 10^9$，$1\le q\le 10^4$。