+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **تیله**، برادر دوقلوی لیته با دیدن وضع موجود به این فکر افتاده که نباید از برادرش عقب بیفتد پس نزد دکتر جیله ( از خوبان امر خیر! ) رفته است و از وی درخواست کرده است به عنوان پدری مهربان و استادی گرانقدر آستین‌هایش را برای این جوان جویای نام بالا بزند. دکتر جیله که به تازگی کار یک نفر دیگر را راه انداخته است، خسته است و فعلا برای تیله یک شرط گذاشته است که باید مسئله سخت زیر را حل کند. فرض کنید یک مجموعه از رشته‌های دودویی (متشکل از ۰ و ۱) داریم، یک گراف جهت‌دار در نظر بگیرید که رأس‌هایش متناظر با این رشته‌ها باشند و از یک رأس مثل $v$ به راس $u$ یال جهت‌دار وجود دارد، اگر و تنها اگر رشته متناظر راس $v$ پیشوندی از رشته متناظر با راس $u$ باشد. **زیبایی** این مجموعه رشته برابر با کمینه تعداد مسیر‌های مجزا رأسی برای پوشاندن همه رأس های گراف به‌دست آمده‌است. حالا تعداد مجموعه‌هایی از رشته‌های دودویی را بیابید که: * مجموع طولشان $n$ است. * زیبایی خود مجموعه برابر $k$ است. سپس باقی‌مانده تقسیم عدد حاصل را بر $10^9 + 7$ محاسبه کنید. دقّت کنید که در مجموعه، عضو تکراری وجود ندارد و ترتیب اعضا مهم نیست. توجه کنید که شما باید به ازای چند مقدار مختلف از $n$‌ و $k$ جواب مسئله را محاسبه کنید. # ورودی خط اول ورودی شامل عدد طبیعی $t$ می‌باشد که نشاندهنده تعداد سوال‌هایی است که شما باید جواب بدهید. در هر یک از $t$ خط بعد دو عدد مثل $n$ و $k$ آمده اند. $$1 \le n \le 50$$ $$1 \le k \le 8$$ $$1 \le t \le 1\ 000$$ # خروجی در $t$ خط مختلف به ازای هر سوال تنها یک عدد چاپ کنید که جواب نهایی آن سوال است. ## ورودی نمونه ``` 3 1 1 4 2 7 3 ``` ## خروجی نمونه ``` 2 18 68 ```

حل سؤال در بانک سؤالات