题目描述

闪耀之塔是一棵节点结点从 $1\sim 2^n -1$ 编号，以 $1$ 为根，共有 $n$ 层的满二叉树。

非叶子节点节点 $i$ 的左右儿子的编号分别为 $i\times2$ 和 $i \times 2 +1$。

多萝茜需要给这颗树上所有节点附上一个权值。

每个节点的权值取值范围为 $[1,2^n-1]$，且要保证互不相同。

定义 $S(u)$ 为 $u$ 节点的所有儿子的集合，$val_u$ 表示节点 $u$ 的权值。

每个节点有一个能量值 $f(u)$，其可表示为：

她想知道在保证 $\sum_{i = 1}^{2^n-1} f(i)$ 取得最大值时，对于编号为 $p$ 的节点其 $f(p)$ 的最大值是多少。 询问的答案需要对 $10^9+7$ 取模。

输入格式

第一行包含两个正整数 $n,q$，分别表示满二叉树的层数和询问的次数。

接下来包含 $q$ 组询问，每组数据的格式如下：

第一行包含一个整数 $k$，表示接下来输入的 01 串的长度。

第二行包含一个的 01 串，为 $p$ 的二进制表示，保证 01 串的首位为 $1$，$p$ 表示所询问的节点编号。

输出格式

对于每次询问：输出一行包含一个整数，表示询问的答案对 $10^9+7$ 取模的结果。

2 1
2
11

3

10 3
4
1001
8
10110110
3
111

84582
5362
163710

提示

【数据范围】

对于所有测试数据，保证：

• $1 \leq k\leq n \leq 10^{12}$；
• $1 \leq q\leq 1000$；
• $1 \leq k\leq 10^4$。

特殊性质 A：保证任意一组的询问都有 $k = 1$。