Рассмотрим скобочные последовательности с одним типом скобок. Для заданной скобочной последовательности найдите количество ее подпоследовательностей, которые являются правильными скобочными последовательностями.

Например, для последовательности "((())())(" таких последовательностей восемь: "((())())", "(())()", "((()))", "(()())", "(())", "()()", "()" и "".

Входные данные

Содержит последовательность, состоящую не более чем из 300 круглых скобок.

Выходные данные

Выведите количество различных правильных скобочных подпоследовательностей заданной последовательности.