Problems
Brackets
Brackets
Consider the bracket sequence with one type of parentheses. For a given sequence bracket find the number of subsequences that are right considerable bracket sequences.
For example, the sequence "((())())(" eight of these subsequences: "((())())", "(())()", "((()))", "(()())", "(())", "()()", "()" and "".
Input
Contains a sequence of no more than 300 parentheses.
Output
Print the number of different correct subsequences in the given bracket sequence.
Input example #1
((())())(
Output example #1
8