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

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

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

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

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

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