به یک رشته از )
و (
یک «پرانتزگذاری معتبر» میگوییم اگر برای هر پرانتز باز بتوان یک پرانتز بسته متناظر کرد به طوری که رشته بین این دو پرانتز تشکیل یک پرانتزگذاری معتبر دهد و با حذف این بازه رشته باقیمانده پرانتزگذاری معتبر باشد.
به یک پرانتز گذاری «-معتبر» میگوییم اگر با اضافه کردن پرانتز باز به ابتدای رشته و پرانتز بسته در انتهای آن، پرانتز گذاری معتبر شود.
تعداد رشتههایی را بیاید که طول آن بوده و -معتبر باشد. چون تعداد این رشته خیلی زیاد است باقیمانده پاسخ مسئله را به چاپ کنید.
در سطر اول ورودی عدد صحیح و مثبت داده میشود و در سطر بعدی هر کدام دو عدد و داده می شود.
خروجی شامل سطر است که در هر سطر تعداد رشته های به طول که -معتبر باشد را چاپ کنید.