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.