Розглянемо послідовності дужок з одним типом дужок. Для заданої послідовності дужок знайдіть кількість її підпослідовностей, які є правильными послідовностями дужок.
Наприклад, для послідовності "((())())(" таких послідовностей вісім: "((())())", "(())()", "((()))", "(()())", "(())", "()()", "()" і "".
Вхідний файл містить послідовність, яка складається не більше ніж з 300 круглих дужок.
Виведіть кількість різни правильних підпослідовностей дужок заданої послідовності.