- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۶۴ مگابایت
سعید \(n\) ماه است که در کوئرا کار میکند. حقوق او در ماه \(i\)ام (\(1 \leq i \leq n\)) برابر \(s_i\) بوده است. او یک شرایط سخت برای ادامه همکاری خود با کوئرا دارد و میخواهد از این به بعد، حقوق هر ماه او برابر مجموع حقوق ماههای قبلی باشد.
به عبارت دیگر:
- حقوق ماه \(n + 1\)ام یا همان \(s_{n+1}\) برابر \(s_1 + s_2 + \dots + s_n \,\)
- حقوق ماه \(n + 2\)ام یا همان \(s_{n+2}\) برابر \(s_1 + s_2 + \dots + s_{n+1} \,\)
- حقوق ماه \(n + 3\)ام یا همان \(s_{n+3}\) برابر \(s_1 + s_2 + \dots + s_{n+2} \,\)
- و...
حال از شما \(q\) سوال میپرسیم. در سوال \(j\)ام از شما میخواهیم میزان حقوق دریافتی این شخص در ماه \(k_j\)ام (یا همان \(s_{k_j}\)) را محاسبه کنید.
چون ممکن است این عدد خیلی بزرگ باشد، باقیمانده این عدد را بر \(10^9+7\) محاسبه کنید.
ورودی
در سطر اول ورودی به ترتیب دو عدد صحیح و مثبت \(n\) و \(q\) آمده است که به ترتیب نشاندهندهی تعداد ماههایی است که سعید تا کنون حقوق گرفته و تعداد سوالاتی که پرسیده خواهد شد. \[1 \leq n, q \leq 100\] در سطر دوم ورودی \(n\) عدد صحیح و مثبت \(s_1, s_2, \dots, s_n\) آمده است که حقوقهای دریافتی سعید در این \(n\) ماه را نشان میدهد. \[1 \leq a_i \leq 100\] در \(q\) سطر بعدی در هر سطر یک عدد صحیح و مثبت \(k_j\) آمده است که یعنی حقوق دریافتی این شخص در ماه \(k_j\)ام را به پیمانه \(10^9 + 7\) محاسبه کنید. \[n + 1 \leq k_j \leq 1000 \ 000 \ 000\]
خروجی
خروجی شامل \(q\) سطر است که در سطر \(j\)ام آن، پاسخ سوال \(j\)ام، یعنی باقیمانده میزان حقوق دریافتی سعید در ماه \(k_j\) بر \(10^9+7\) را چاپ کنید.
مثال
ورودی نمونه ۱
3 2
1 2 3
4
5
خروجی نمونه ۱
6
12
حقوق ماه ۴ام او ۶ و حقوق ماه ۵ام برابر ۱۲ است.
ورودی نمونه ۲
5 1
1 1 1 1 1
1401
خروجی نمونه ۲
349521860
توجه کنید پاسخ اصلی مسئله یک عدد بسیار بزرگ است، اما در این سوال کافی است باقیمانده این عدد را بر \(10^9+7\) محاسبه کنید.