J. Антон и школа
Скобочную последовательность назовём простой правильной, если она непуста, её длина чётна, первая половина состоит только из символов (, а вторая — только из ). Например, ((())) простая правильная, а (()) и ()() — нет.
Дана скобочная последовательность . Посчитайте, сколько у неё различных подпоследовательностей, являющихся простыми правильными.
Подпоследовательность получается вычёркиванием символов. Две подпоследовательности различны, если различаются множества вычеркнутых позиций.
Перебирать длину и позиции нельзя — их слишком много. Зафиксируйте последнюю открывающую скобку ответа: тогда всё, что слева, выбирается из открывающих до неё, а всё, что справа, — из закрывающих после.
Формат ввода
Одна строка содержит непустую последовательность из символов ( и ) длиной не более .
Формат вывода
Одно число — количество простых правильных подпоследовательностей по модулю .
Примеры
)(()()
6
()()()
7
)))
0