题目描述

最近$DD$正在研究括号。 对于一个合法的括号序列$($合法括号满足的条件为左边第一个括号必须为$($其次满足$($个数等于$)$个数，这样称为合法括号$)$,$DD$只会进行两种操作。

• 删除一个左括号
• 删除一个有括号，使得剩下的括号序列合法

$DD$想请你帮他计算出有多少种方案可以将序列删成空串。

输出描述

一行 一个合法的括号序列 序列长度$(\leq 20)$

输出描述

一个整数,方案数

输入样例1

()()

输出样例1

1

输入样例2

((()))

输出样例2

24