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

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