• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۶۴ مگابایت

سعید $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$ محاسبه کنید.