Юна програмістка Агнеса нещодавно взнала на уроці інформатики про арифметичні вирази. Вона зацікавилась питанням, що ж буде, якщо з арифметичного виразу видалити все, крім дужок. Увівши запит у своєму улюбленому пошукувачеві, вона вияснила, що математики називають послідовності дужок, які могли б зутрітись у деякому арифметичному виразі, правильними дужковими послідовностями.
Так, послідовність ()(()) є правильною дужковою послідовністю, тому що вона може, наприклад, зустрічатись у виразі (2+2):(3–(5–2)+4), а послідовності (() і ())( не є такими. Легко бачити, що існує п'ять правильних дужкових послідовностей, які складаються рівно з шести дужок (по три дужки кожного типу — відкриваючих і закриваючих): ((())), (()()), (())(), ()(()) и ()()().
Агнеса зацікавиалась найпростішими перетвореннями правильних дужкових послідовностей. Для початку Агнеса вирішила обмежитись додаванням дужок у послідовність. Вона дуже швидко вияснила, що після додавання однієї дужки послідовність перестає бути правильною, а ось додавання двох дужок іноді зберігіє властивість правильності. Наприклад, при додаванні двох дужок у різні місця послідовності ()() можна отримати послідовності (()()), (())(), ()(()) і ()()(). Легко бачити, що при довільному способі додавання двох дужок із збереженням властивості правильності одна з нових дужок повинна бути відкриваючою, а друга — закриваючою.
Агнеса хоче підрахувати кількість різних способів додавання двох дужок у задану правильну дужкову послідовність так, щоб знову отримувалась правильна дужкова послвдовнвсть. На жаль, виявилось, що ця кількість може бути у деяких випадках дуже великою. Агнеса розрізняє способи отримання послідовності за позиціями доданих дужок у отриманій послідовності. Наприклад, навіть при додаванні дужок у найпростішу послідовність () можна отримати іншу правильну дужкову послідовність сімома способами: ()(), (()), (()), (()), (()), ()(), ()(). Туть додані дужки виділено жирним шрифтом.
Таким чином, якщо в отриманій послідовності додана відкриваюча дужка стоіть у позициї i, а додана закриваюча — у позиції j, то два способи, що відповідають парам (i_1, j_1) та (i_2, j_2), вважаються різними, якщо i_1≠i_2 або j_1≠j_2.
Потрібно написати програму, яка за заданою правильною дужковою послідовністю визначає кількість різних описаних вище способів додавання двох дужок.
Вхідний файл складається з одного непустого рядкаи, який містить рфвно 2n символів: n відкриваючих і n закриваючих круглих дужок. Гарантується, що цей рядок є правильною дужковою послідовністю.
Величина n (кількість дужок кожного типу) не перевищує 50000.
Виведіть у вихідний файл кількість різних способів додавання у задану послідовність двох дужок таким чином, щоб отримати іншу правильну дужкову послідовність.