عادة يسم Farmer John أبقاره بعلامة دائرية، لكن حديد الوسم مكسور فيستخدم قوسًا (. لديه سلالتا Holstein وGuernsey. كل بقرة تحمل القوس، ويبدو أيسر أو أيمن بحسب اتجاهها.
تقف الأبقار $N$ في صف باتجاهات عشوائية، فتبدو العلامات سلسلة أقواس بطول $N$. يلاحظ FJ أن قراءة Holstein فقط من اليسار لليمين بترتيب ظهورها تعطي سلسلة متوازنة، وكذلك Guernsey! لمعرفة ندرة هذا، احسب طرق إسناد السلالات للأبقار $N$ لتحقق الخاصية.
للتوازن تعريفات عدة. الأبسط أن عدد ( و) الإجمالي متساوٍ، وفي كل بادئة عدد ( لا يقل عن ). مثلًا هذه السلاسل متوازنة:
() (()) ()(()())
وهذه ليست كذلك:
)( ())( ((())))
الإدخال
- السطر 1: سلسلة أقواس بطول $N$ $(1 \le N \le 1000)$.
الإخراج
- السطر 1: عدد صحيح لطرق الإسناد بحيث تشكل Holstein وGuernsey كل منهما متتالية جزئية من أقواس متوازنة. قد تكبر الإجابة، فاطبع باقي قسمتها على 2012، أي بترديد 2012. إسناد سلالة واحدة فقط صالح.
أمثلة
الإدخال 1
(())
الإخراج 1
6
ملاحظة
الإسنادات التالية صالحة:
(()) HHHH
(()) GGGG
(()) HGGH
(()) GHHG
(()) HGHG
(()) GHGH
مؤلف المسألة: Brian Dean، 2012