A diagnostic tool encodes a nested amplifier chain as a string of only ( and ) characters, guaranteed to be balanced (every prefix has at least as many ( as ), and the total counts are equal). The chain's signal score is defined recursively:

• () (a single directly-adjacent pair) has score 1.
• If AB is the concatenation of two balanced pieces A followed by B (each balanced on its own), its score is score(A) + score(B).
• If a balanced piece has the form (A) (a single pair wrapping a balanced piece A), its score is 2 * score(A).

Compute the signal score of the whole given string.

Input format

Line 1: the balanced parentheses string.

Output format

A single integer: the signal score of the string.

Constraints

• 2 ≤ length of the string ≤ 5000, and the length is always even.
• The string is guaranteed balanced.

()

1

(())

2