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