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

---

به یک رشته از ) و ( یک «پرانتزگذاری معتبر» می‌گوییم اگر برای هر پرانتز باز بتوان یک پرانتز بسته متناظر کرد به طوری که رشته بین این دو پرانتز تشکیل یک پرانتزگذاری معتبر دهد و با حذف این بازه رشته باقی‌مانده پرانتزگذاری معتبر باشد.

به یک پرانتز گذاری «$k$-معتبر» می‌گوییم اگر با اضافه کردن $k$ پرانتز باز به ابتدای رشته و $k$ پرانتز بسته در انتهای آن، پرانتز گذاری معتبر شود.

تعداد رشته‌هایی را بیاید که طول آن $2n$ بوده و $k$-معتبر باشد. چون تعداد این رشته خیلی زیاد است باقی‌مانده پاسخ مسئله را به $10^9 + 7$ چاپ کنید.

ورودی

در سطر اول ورودی عدد صحیح و مثبت $t$ داده می‌شود و در $t$ سطر بعدی هر کدام دو عدد $n$ و $k$ داده می شود. $$1 \le t \le 10^5$$ $$0 \le k \le 10^6$$ $$1 \le n \le 10^6$$

خروجی

خروجی شامل $t$ سطر است که در هر سطر تعداد رشته های به طول $2n$ که $k$-معتبر باشد را چاپ کنید.

مثال

ورودی نمونه ۱

3
2 1
4 2
5 3

خروجی نمونه ۱

5
62
242