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

---

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

به یک پرانتز گذاری «\(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