There are total $N+1$ squares numbered from $0$ to $N$. You start at square $0$. Also there are $L$ ladders, where i-th ladder is denoted by two integers: $a_i \: b_i$, it means that the ladder starts at square $a_i$ and ends at $b_i$ ( $a_i < b_i$ ). There is no such square where more than one ladder starts, and also, the starting square of any ladder is not the same as the ending square of any other ladder. Now in every move, you can move ahead by  1, 2, 3, 4, 5 or 6 squares. If you land on a square where any ladder starts, then you will climb that ladder and directly get transported to the square where that ladder ends. You cannot move beyond square $N$, (for e.g., if you are at square $N-1$, then you have only one option - to move to square $N$).

For each ladder $i$, you have to find out the number of ways to reach from square $0$ to square $N$, in which you have climbed (used) ladder $i$. It doesn't matter if you used the other ladders or not. Since the answer can be large, print your answer modulo $10^9+7$.

Input

• The first line of input contains two space-separated integers: $N \: L$, the last square and the number of ladders.
• Each $i^{th}$ line of next $L$ lines contains two space-separated integers: $a_i \: b_i$, the starting and ending squares of ladder $i$.

Output

Print $L$ lines, the $i^{th}$ of which contains a single integer - the number of ways to reach the square N while having climbed ladder $i$ (modulo $10^9+7$). Also print a new-line at the end.

Constraints

• $1 \le N \le 10^5$
• $1 \le L \lt N$
• For any two ladders $i$ and $j$, $a_i \ne a_j$ and $b_i \ne a_j$ and $b_j \ne a_i$