+ محدودیت زمان: ۳ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
+ منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر
----------
مادربزرگ می خواهد به مناسبت کسب مدال طلای جهانی(*fullmark*) توسط تمامی $n$ نوه اش به آنها جایزه بدهد. او آنها را پشت سر هم در یک ردیف و از چپ به راست نشانده است. مادربزرگ کمی حواس پرت هست و به طور ناگهانی یادش می آید که باید به بازه $l$ تا $r$ از نوه هایش جایزه بدهد و برای این کار به نفر اول(نفر $l$ ام) یک سکه به نفر بعد ۲ سکه و به نفر آخر(نفر $r$ ام) $r - l + 1$
سکه می دهد.
هر از گاهی هم مادربزرگ کنجکاو است که بداند مجموع تعداد سکه های بازه $l$ تا $r$ از نوه هایش چقدر می باشد.به مادربزرگ کمک کنید!
# ورودی
در خط اول ورودی دو عدد $n$ و $q$ آمده است که تعداد نوه های مادربزرگ و تعداد عملیات های مادربزرگ می باشد!
در خط بعدی $n$ عدد آمده است که تعداد سکه های اولیه نوه های مادربزرگ به ترتیب از چپ به راست می باشد.این اعداد بین $0$ تا $10^9$ می باشند.
در $q$ خط بعدی در هر خط ابتدا رشته $t$ و سپس $l$ و $r$ آمده است.
اگر
$t=ask$
باقیمانده مجموع تعداد سکه های نوه های بین بازه $l$ تا $r$ بر
$10^9+7$
را چاپ کنید.
اگر
$t=add$
مادربزرگ به بازه ی $l$ تا $r$ از نوه هایش به شکل گفته شده سکه می دهد.
$$1 \le l \le r \le n \le 200\ 000$$
# خروجی
به ازای هر یک از عملیات های $ask$ جواب را چاپ کنید.
# زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت
|:------------------:|:----------:|:------------------:|
| ۱ | ۳۰ | $1\le n,q \le 2\ 000$ |
| ۲ | ۲۰ | $,1\le n \le 2\ 000$ $1 \le q \le 200\ 000$ |
| ۳ | ۵۰ | بدون محدودیت اضافی |
# مثال
## ورودی نمونه ۱
```
5 10
4 7 4 7 4
ask 1 5
add 1 2
ask 2 4
add 3 5
ask 4 5
add 2 5
add 3 3
ask 3 3
ask 2 5
ask 1 5
```
## خروجی نمونه ۱
```
26
20
16
8
41
46
```
(آزمون آزمایشی ۲۴ مین دوره المپیاد کامپیوتر-دوره تابستان المپیاد کامپیوتر ۱۳۹۳)