+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک آرایه از اعداد صحیح مثل $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 ``` <details class="blue"> <summary> **راهنمایی اول** </summary> ---------- نیازی نیست همه‌ی تغییرات را در لحظه روی آرایه اعمال کنیم. می‌توانیم همه را دریافت کنیم و با ترتیبی مناسب آن‌ها را روی آرایه اعمال کنیم. </details> <details class="blue"> <summary> **راهنمایی دوم** </summary> ---------- اگر لحظه‌ی شروع و پایان هر بازه که باید تغییر کند را روی آرایه در نظر بگیریم و به ترتیب از چپ آرایه (اندیس ۰) شروع کنیم و به سمت راست (اندیس $n - 1$) حرکت کنیم و همه‌ی تغییرات را به همین ترتیب روی آرایه اعمال کنیم. به این ایده *sweep line* می‌گویند. </details> <details class="blue"> <summary> **راهنمایی سوم** </summary> ---------- با توجه به رابطه بازگشتی فیبوناچی که برای همه یکی هست می‌توان اتفاق این تغییرات را جمع کرد. یعنی اگر چند تغییر روی یک خانه اتفاق می‌افتد می‌توان همه‌ی آن‌ها را باهم جمع کرد. </details>

حل سؤال در بانک سؤالات