پرانتزگذاری در کوئرا


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

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

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

تعداد رشته‌هایی را بیاید که طول آن 2n2n بوده و kk-معتبر باشد. چون تعداد این رشته خیلی زیاد است باقی‌مانده پاسخ مسئله را به 109+710^9 + 7 چاپ کنید.

ورودی🔗

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

خروجی🔗

خروجی شامل tt سطر است که در هر سطر تعداد رشته های به طول 2n2n که kk-معتبر باشد را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
2 1
4 2
5 3
Plain text

خروجی نمونه ۱🔗

5
62
242
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.