Fibonacci and Sequence and Queries

The Fibonacci numbers start with $0$ and $1$. The $0$-th Fibonacci number is $0$, and the $1$-st Fibonacci number is $1$. From the $2$-nd Fibonacci number onward, each is the sum of the two immediately preceding Fibonacci numbers. As a formula, $F_n = F_{n-2} + F_{n-1}$ ($n \geq 2$).

A single $n$-th Fibonacci number is easy to compute with the recurrence above, but this problem is not so simple. You are given a sequence of length $N$ in which every value is $0$. Write a program that prints the result after performing the following queries.

• l r: add $F_1, F_2, ..., F_{r-l+1}$ to positions $l$ through $r$ of the sequence, respectively.

The first line gives the size of the sequence, $N$. ($1 \leq N \leq 1\ 000\ 000$)

The second line gives the number of queries, $Q$. ($1 \leq Q \leq 100\ 000$)

Starting from the third line, $Q$ lines each give the information $l$, $r$ for a query. ($1 \leq l \leq r \leq N$)

After applying all queries, print all numbers of the sequence separated by spaces. Since the numbers can get very large, print each number modulo $10^9+7$.