题目背景

小k 正在 ACM 的赛场上做着经典的括号匹配题目，突然可恶的宇宙射线打乱了他的题目，导致他只能看到原序列的一部分。

小k 想知道，在所有宇宙射线的可能性中，有多少种可能的子序列是非空有效的括号序列。

题目描述

给定一个仅由 ( 和 ) 组成的字符串 。请计算该字符串的子序列中，有多少个是非空有效括号序列。

有效括号序列定义如下：

1. 空字符串是有效序列。
2. 如果 A 是有效序列，则 (A) 也是有效序列。
3. 如果 A 和 B 都是有效序列，则 AB 也是有效序列。

注意：

• 子序列是指从原字符串中删除零个或多个字符后剩余字符保持原相对顺序形成的序列。
• 不同的位置选取的字符即使相同，也视为不同的子序列方案。
• 空子序列不计入答案（即结果需减去空序列的一种情况，或仅计算非空有效序列）。

输入格式

一个长度为 $n$ 的字符串 $s$ 。 满足 $1 \leq n \leq 26$。

输出格式

一个整数，表示非空有效括号子序列的总数。

样例

()()

4

样例解释

在字符串 ()() 中，有效的非空子序列有：

1. 选取下标 $0,1$ 得到 ()
2. 选取下标 $2,3$ 得到 ()
3. 选取下标 $0,1,2,3$ 得到 ()()
4. 选取下标 $0,3$ 得到 ()