====== Parentheses ======

یک رشته‌ي کامل را به صورت زیر تعریف می‌کنیم:

  * () یک رشته‌ی کامل است.
  * [] یک رشته‌ی کامل است.
  * اگر $S$ یک رشته‌ی کامل باشد، ($S$) یک رشته‌ی کامل است.
  * اگر $S$ یک رشته‌ی کامل باشد، [$S$] یک رشته‌ی کامل است.
  * اگر $S$, $T$ رشته‌های کامل باشند، ST نیز که از قراردادن $T$ به دنبال $S$ به‌دست  می‌آید، رشته‌ای کامل است.

هر رشته‌ی کامل را می‌توان به این صورت ناقص کرد که تمام کاراکترهای '[' و ']' آن را به ')' تبدیل کرد. به شما از ورودی یک رشته‌ی ناقص داده می‌شود. شما باید تعداد رشته‌های کاملی را پیدا کنید که ناقص آن‌ها، برابر با رشته‌ی ورودی باشد. 
===== ورودی =====

  * ابتدا $n$ (طول رشته) به شما داده می‌شود. سپس رشته‌ی ورودی به شما داده می‌شود.
  * $1 \leq n \leq 10000$
===== خروجی =====

شما باید باقی‌مانده‌ی تعداد رشته‌های خواسته شده را در تقسیم بر 1,000,000,009  بیابید.

===== محدودیت‌ها =====

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

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|4 \\ ((() | 2|
</WRAP>


<پاسخ>
منتظر پر کردن این قسمت توسط علاقمندان هستیم.
</پاسخ>

  * [[سوال ۳۷|سوال بعد]]
  * [[سوال ۳۵|سوال قبل]]