칡덩굴 베기

이제 부정할 수 없다. 정원의 칡덩굴이 통제 불능으로 자라 버렸다. 몇 년 전 수학 선생님께 선물로 받은 새싹 하나를 심었다. 선생님이 설명해 준 성장 방식이 어렴풋이 기억난다.

• 뿌리 정점 하나에서 시작하며, 번호는 $0$이다.
• 해마다 새로운 정점과 간선이 자란다. 해가 시작될 때 정점이 $n$개라면, 그해 동안 $n$개의 정점 각각에서 새로운 간선 하나와 정점 하나가 자란다. 기존 정점의 번호가 $v$라면, 그 정점에서 자란 새 정점의 번호는 $v+n$이다.
• $i$년이 지나면 칡덩굴에는 정확히 $2^i$개의 정점이 있고, 번호는 $0$부터 $2^i-1$까지라는 것을 보일 수 있다.

이제 칡덩굴에서 여러 가지(부분 트리)를 하나씩 잘라 낼 차례다. 멋진 모양으로 나무를 다듬을 계획이지만, 칡덩굴이 워낙 빨리 자라니 그 모양이 오래 유지되지는 않겠다. 그래도 매년 계속 다듬겠다고 스스로에게 약속한다. 오늘 잘라 낼 가지를 정한 뒤, Branching And Pruning Company에 전화해 식물 폐기물을 처리해 달라고 부탁한다. 회사는 정확히 얼마나 치워야 하는지 알고 싶어 한다. 계산할 수 있을 것 같지만, 어떻게 해야 할까?

어떤 정점 $v$를 뿌리로 하는 부분 트리를 제거한다는 것은, 정점 $v$와 그로부터 자란 모든 정점(그리고 그 정점들로부터 자란 정점들, 계속해서)을 제거한다는 뜻이다. 그림 K.1은 두 번째 예제에 대한 이 과정을 보여 준다.

제거할 부분 트리들의 뿌리 번호가 주어질 때, 제거되는 각 부분 트리마다 제거되는 정점의 수를 계산하라. 이 수가 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구해야 한다.

그림 K.1: 두 번째 예제의 나무. 색은 각 정점이 어느 제거에서 사라지는지를 나타낸다.

입력은 다음과 같다.

• 한 줄에 정수 두 개 $a$ ($0 \leq a \leq 10^6$)와 $m$ ($1 \leq m \leq 10^5$)가 주어진다. $a$는 나무의 나이(년)이고, $m$은 제거할 부분 트리의 수이다.
• $m$개의 줄이 이어지며, 각 줄에 정수 $v$ ($0 \leq v \leq 10^9$)가 주어진다. $v$는 나무에서 제거할 정점의 번호이다. $v$가 아직 제거되지 않았음이 보장된다.

$m$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 제거에서 제거되는 정점의 수를 $10^9+7$로 나눈 나머지를 출력한다.