점호

시우 장군의 부대엔 $2^N$명의 병사와 $N$ 종류의 장비가 있다. 병사들은 각 종류의 장비를 보유하고 있거나 보유하고 있지 않다. 또한, 임의로 두 병사를 골랐을 때 보유 중인 장비의 목록이 정확히 같은 경우는 존재하지 않는다.

시우 장군은 매일 $2N$가지 유형의 서로 다른 점호를 실시한다. $2i-1$번 유형의 점호에선 장비 $i$를 보유한 병사만 소집하며, $2i$번 유형의 점호에선 장비 $i$를 보유하지 않은 병사만 소집한다. 각 점호 사이의 혼란을 방지하기 위해, 직전 점호 인원 중 절반이 넘게 소집해제되는 경우가 없도록 점호 순서를 정해야 한다.

또한 매번 동일한 순서로 점호를 실시하는 것은 보안 상 좋지 않아서, 시우 장군은 $x$번 유형의 점호를 $y$번째로 실시할 수 있는 점호 순서들 중, 사전 순으로 가장 빠른 것을 채택하고 있다.

가능한 점호 순서가 매우 많기 때문에, 시기오시 장군은 자신이 점호 순서를 올바르게 계산했는지 검증하고 싶다. $a\_k$가 $k$번째로 실시한 점호의 유형이라 하자. $x$와 $y$가 주어질 때마다, $\displaystyle\sum\_{k=1}^{2N}\left(k\times a\_k\right)$를 $10^9+7$로 나눈 나머지를 계산하여 출력하여라.

첫 번째 줄에는 $N, Q$가 순서대로 주어진다. ($2 \le N \le 10^9$, $1\le Q\le 200\\,000$)

두 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 2개의 $x, y$가 입력된다. ($1 \le x, y \le 2N$)

각 쿼리는 이후의 쿼리에 영향을 주지 않음에 주의하라.

$Q$개의 줄에 걸쳐 각 줄마다 해당 $x, y$에 대한 답을 출력한다.