26272번 - 점호

문제

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

시우 장군은 매일 2ドルN$가지 유형의 서로 다른 점호를 실시한다. 2ドルi-1$번 유형의 점호에선 장비 $i$를 보유한 병사만 소집하며, 2ドルi$번 유형의 점호에선 장비 $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$에 대한 답을 출력한다.

제한

힌트