+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- به یک رشته از `)` و `(` یک «پرانتزگذاری معتبر» می‌گوییم اگر برای هر پرانتز باز بتوان یک پرانتز بسته متناظر کرد به طوری که رشته بین این دو پرانتز تشکیل یک پرانتزگذاری معتبر دهد و با حذف این بازه رشته باقی‌مانده پرانتزگذاری معتبر باشد. به یک پرانتز گذاری «$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 ```