Дужки

Розглянемо послідовності дужок з одним типом дужок. Для заданої послідовності дужок знайдіть кількість її підпослідовностей, які є правильными послідовностями дужок.

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

Вхідні дані

Вхідний файл містить послідовність, яка складається не більше ніж з 300 круглих дужок.

Вихідні дані

Виведіть кількість різни правильних підпослідовностей дужок заданої послідовності.

Приклади