题目背景

你花园里的葛藤已经彻底失控。多年前，你种下了一株幼苗。它的生长方式如下：

• 初始时只有一个根节点，编号为 $0$；
• 每一年开始时，如果当前有 $n$ 个节点，那么这一年会从每个已有节点长出一条新边和一个新节点；
• 如果旧节点编号为 $v$，新长出的节点编号为 $v+n$。

可以证明，经过 $i$ 年后，葛藤共有 $2^i$ 个节点，编号为 $0$ 到 $2^i-1$。

现在你决定依次砍掉若干棵以指定节点为根的子树。每次砍掉一棵子树后，这棵子树中的所有节点都会被移除。你需要计算每次操作实际移除了多少个尚未被移除的节点。

题目描述

给定葛藤年龄 $a$，以及 $m$ 次修剪操作。第 $i$ 次操作给出一个节点 $v$，表示砍掉以 $v$ 为根的整棵子树。

题目保证每次给出的 $v$ 在操作发生时尚未被移除。

对于每次操作，输出本次实际移除的节点数量。答案可能很大，需要对 $10^9+7$ 取模。

输入格式

第一行包含两个整数 $a,m$，分别表示葛藤年龄和修剪次数。

接下来 $m$ 行，每行包含一个整数 $v$，表示本次要砍掉的子树根节点。

输出格式

输出 $m$ 行。

第 $i$ 行输出第 $i$ 次修剪实际移除的节点数，对 $10^9+7$ 取模。

样例 1

输入

4 1
0

输出

16

样例 2

输入

3 4
4
3
1
0

输出

1
2
2
3

样例 3

输入

5 5
6
3
1
18
2

输出

4
8
8
1
3

样例 4

输入

42 1
0

输出

46480318

数据范围

保证每次操作给出的节点在当前时刻尚未被移除。