+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
یک آرایه از اعداد صحیح مثل $a_1, a_2, \dots, a_n\,$ داریم. در $q$ مرحله یک عملیات مثل زیر روی آن انجام می‌دهیم.
دو عدد صحیح مثل $\ell$ و $r$ انتخاب می‌کنیم که $1 \leq \ell \leq r \leq n$ باشد و سپس مقدار
+ $a_{\ell} = a_{\ell} + fib_1$
+ $a_{\ell + 1} = a_{\ell + 1} + fib_2$
+ $\dots$
+ $a_r = a_r + fib_{r-\ell + 1}$
می‌شود که منظور از $fib_i$ جمله‌ی $i$ام دنباله فیبوناچی است. دنباله فیبوناچی به صورت زیر تعریف می‌شود:
$$
fib_n = \begin{cases}
1 & n = 1 \\
1 & n = 2 \\
fib_{n - 1} + fib_{n - 2} & n > 2
\end{cases}
$$
از شما می‌خواهیم بعد از پایان این عملیات‌ها، مقدار نهایی اعضای آرایه را چاپ کنید. چون این مقدار می‌تواند خیلی بزرگ باشد. صرفاً باقی‌مانده هر عدد آرایه را بر $10^9 + 7$ چاپ کنید.
# ورودی
در سطر اول ورودی، دو عدد صحیح و مثبت $n$ و $q$ که با یک فاصله از هم جدا شده‌اند، داده می‌شود.
$$1 \leq n, q \leq 100 \, 000$$
در سطر دوم ورودی، $n$ عدد صحیح $a_1, a_2, \dots, a_n\,$ که با یک فاصله از هم جدا شده‌اند داده می‌شود.
$$1 \leq a_i \leq 10^9$$
در $q$ سطر بعدی، در هر سطر دو عدد صحیح $\ell$ و $r$ داده می‌شود که نشان‌دهنده‌ی بازه‌ی عملیات است.
$$1 \leq \ell \leq r \leq n$$
# خروجی
در تنها سطر خروجی، $n$ عدد صحیح که با یک فاصله از هم جدا شده‌اند را چاپ کنید که وضعیت نهایی آرایه‌ی $a$ را نشان می‌دهد.
چون ممکن است مقدار اعداد آرایه خیلی بزرگ شود، باقی‌مانده‌ی این اعداد را بر $10^9 + 7$ چاپ کنید.
# مثال‌ها
## ورودی نمونه ۱
```
5 3
1 2 3 4 5
2 4
1 3
5 5
```
## خروجی نمونه ۱
```
2 4 6 6 6
```
## ورودی نمونه ۲
```
3 2
2 4 1
1 3
2 3
```
## خروجی نمونه ۲
```
3 6 4
```