شرکت آقای مهندس از معدود شرکت‌های عمرانی است که قادر به تخریب ساختمان‌های قدیمی به صورت طبقهای است. تخریب طبقهای یک ساختمان، به معنای تخریب طبقه‌های آن ساختمان به ترتیب از بالاترین طبقه تا طبقه‌ی اول است. در واقع در این روش کل ساختمان، با استفاده از ماده‌های انفجاری به یک‌باره تخریب نمی‌شود.
گاهی این شرکت باید چندین ساختمان را تخریب کند و برای همین از چند گروه تخریب‌گر برای خراب کردن آن‌ها استفاده می‌کند. می‌دانیم هر گروه در هر روز قادر به تخریب بالاترین طبقه‌ی یک ساختمان است. به یک مجموعه از ساختمان‌ها $(k, d)$-تخریب‌پذیر می‌گوییم، اگر بتوان با $k$ گروه تخریب‌گر و در حداکثر $d$ روز تمامی ساختمان‌های آن را تخریب کرد یعنی هیچ طبقهای از آن‌ها باقی نمانده باشد. دقت کنید که برای انجام یک پروژه‌ی تخریب، در ابتدای هر روز به هر یک از گروه‌ها یکی از ساختمانهایی که هنوز کاملا تخریب نشده (تعداد طبقه‌هایش بیشتر از صفر است) محول می‌شود و در پایان آن روز بالاترین طبقه‌ی آن ساختمان تخریب می‌شود. می‌توان به بعضی از گروه‌ها در ابتدای یک روز هیچ ساختمانی اختصاص نداد. هم‌چنین در یک روز هیچ دو گروهی نباید مشغول تخریب یک ساختمان شوند. بنابراین با در نظر گرفتن این محدودیت‌ها، بعد از گذشت یک روز، تعداد ساختمانهایی که مورد تخریب قرار می‌گیرند حداکثر $k$ تا هستند و از هر کدام از آن‌ها حداکثر یک طبقه تخریب می‌شود.
حال آقای مهندس تمامی ساختمان‌های شهر را بررسی و $n$ تا از آن‌ها را به عنوان ساختمان‌های فرسوده‌‌ی شناسایی کرده است. او از شما خواسته تا برنامه‌ای بنویسید که به پرسش‌هایی از قبیل «تعداد زیر‌مجموعه‌های ناتهی از ساختمان‌های فرسوده که $(k, d)$-تخریب‌پذیر است، چند تاست؟» با توجه به این‌که ممکن است پاسخ به پرسش‌ها عدد بزرگی باشد، کافی است باقی‌مانده‌ی این مقدار را بر $10^9 + 7$ محاسبه کنید.
خروجی شامل $q$ سطر است که در سطر $i$ام از آن پاسخ به پرسش $i$ام آقای مهندس آمده است.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 5 5 1 2 3 4 5 1 2 2 3 3 4 4 5 5 1 | 2 7 15 31 1 |