• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

یک آرایه از اعداد صحیح مثل \(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