Задачи
Скобки
Скобки
Юная программистка Агнесса недавно узнала на уроке информатики об арифметических выражениях. Она заинтересовалась вопросом, что случится, если из арифметического выражения удалить всё, кроме скобок. Введя запрос в своём любимом поисковике, она выяснила, что математики называют последовательности скобок, которые могли бы встречаться в некотором арифметическом выражении, \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{i}, а добавленная закрывающая --- в позиции \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
Выведите в выходной файл количество различных способов добавления в заданную последовательность двух скобок таким образом, чтобы получилась другая правильная скобочная последовательность.
Входные данные #1
()()()
Выходные данные #1
31