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