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

---

تیله، برادر دوقلوی لیته با دیدن وضع موجود به این فکر افتاده که نباید از برادرش عقب بیفتد پس نزد دکتر جیله ( از خوبان امر خیر! ) رفته است و از وی درخواست کرده است به عنوان پدری مهربان و استادی گرانقدر آستین‌هایش را برای این جوان جویای نام بالا بزند.

دکتر جیله که به تازگی کار یک نفر دیگر را راه انداخته است، خسته است و فعلا برای تیله یک شرط گذاشته است که باید مسئله سخت زیر را حل کند.

فرض کنید یک مجموعه از رشته‌های دودویی (متشکل از ۰ و ۱) داریم، یک گراف جهت‌دار در نظر بگیرید که رأس‌هایش متناظر با این رشته‌ها باشند و از یک رأس مثل $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