شرکت آقای مهندس از معدود شرکت‌های عمرانی است که قادر به تخریب ساختمان‌های قدیمی به صورت طبقه‌‌‌ای‌ است. تخریب طبقه‌ای یک ساختمان، به معنای تخریب طبقه‌های آن ساختمان به ترتیب از بالاترین طبقه‌ تا طبقه‌ی اول است. در واقع در این روش کل ساختمان، با استفاده از ماده‌های انفجاری به یک‌باره تخریب نمی‌شود.

گاهی این شرکت باید چندین ساختمان را تخریب کند و برای همین از چند گروه تخریب‌گر برای خراب کردن آن‌ها استفاده می‌کند. می‌دانیم هر گروه در هر روز قادر به تخریب بالاترین طبقه‌ی یک ساختمان است. به یک مجموعه‌ از ساختمان‌ها $(k, d)$-تخریب‌پذیر می‌گوییم، اگر بتوان با $k$ گروه تخریب‌گر و در حداکثر $d$ روز تمامی ساختمان‌های آن را تخریب‌ کرد یعنی هیچ طبقه‌ای از آن‌ها باقی نمانده باشد. دقت کنید که برای انجام یک پروژه‌ی تخریب، در ابتدای هر روز به هر یک از گروه‌ها یکی از ساختما‌ن‌هایی که هنوز کاملا تخریب نشده‌ (تعداد طبقه‌هایش بیشتر از صفر است) محول می‌شود و در پایان آن روز بالاترین طبقه‌ی آن ساختمان تخریب می‌شود. می‌توان به بعضی از گروه‌ها در ابتدای یک روز هیچ ساختمانی اختصاص نداد. هم‌چنین در یک روز هیچ‌ دو گروهی نباید مشغول تخریب یک ساختمان شوند. بنابراین با در نظر گرفتن این محدودیت‌ها، بعد از گذشت یک روز، تعداد ساختمان‌هایی که مورد تخریب قرار می‌گیرند حداکثر $k$ تا هستند و از هر کدام از آن‌ها حداکثر یک طبقه تخریب می‌شود.

حال آقای مهندس تمامی‌ ساختمان‌های شهر‌ را بررسی و $n$ تا از آن‌ها را به عنوان ساختمان‌های فرسوده‌‌ی شناسایی کرده است. او از شما خواسته تا برنامه‌ای بنویسید که به پرسش‌هایی از قبیل «تعداد زیر‌مجموعه‌های ناتهی از ساختمان‌های فرسوده که $(k, d)$-تخریب‌پذیر است، چند تاست؟» با توجه به این‌که ممکن است پاسخ به پرسش‌ها عدد بزرگی باشد، کافی است باقی‌مانده‌ی این مقدار را بر $10^9 + 7$ محاسبه کنید.

• در سطر اول ورودی به ترتیب دو عدد طبیعی $n$، تعداد ساختمان‌های فرسوده‌، و $q$، تعداد پرسش‌های آقای مهندس، آمده است.
• سطر دوم ورودی‌ شامل دنباله‌ی $f_1, f_2, \cdots, f_n$ که نشان‌دهنده‌ی تعداد طبقات ساختمان‌های فرسوده است.
• در هر یک از $q$ سطر بعدی به ترتیب دو مقدار $k$ و $d$ مربوط به پرسش‌ $i$ام آمده است.
• $1 \leq n \leq 400$
• $1 \leq q \leq 200000$
• $1 \leq f_1, f_2, \cdots , f_n \leq 400$
• $1 \leq d \leq 160000, 1 \leq k \leq n$

خروجی شامل $q‌$ سطر است که در سطر $i$ام از آن پاسخ به پرسش $i$ام آقای مهندس آمده است.

• زیرمسئله اول (۱۰ نمره): $k = 1$
• زیرمسئله دوم (۱۰ نمره): $n ≤ 15$ و $q \leq 1000$
• زیرمسئله دوم (۳۰ نمره): $n \leq 50$ و $f_i \leq 50$
• زیرمسئله سوم (۵۰ نمره): بدون محدودیت اضافی

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

• سوال بعد