Bracket

Interview

Time limit2sMemory limit512 MB

Summary

Given a bracket pattern with some fixed brackets and some dots, count the ways to fill the dots so the whole string is a balanced bracket sequence.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, String, Prefix sum
Solved: No attempts yet

Problem

Brackets are given at certain positions. By adding opening brackets “(” and closing brackets “)” in place of “.”, form valid bracket expressions. Find the number of all valid expressions.

Input

Several strings of even length containing dots and the brackets "(" and ")" are given. One expression per line.

Output

Output the results as natural numbers, one per line, in the order of the strings.

Constraints

The number of input tests does not exceed 200, and the length of a single line does not exceed 1000.

Examples1

Example 1

Input

...(
..).
....
..........)...

Expected output