Competitions

# February 21 - March 3. Dynamic Programming

# 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