Competitions

# 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.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
((())())(

Output example #1
8