站外题求解

给定一个只包含一种括号的括号序列，求这个序列中有多少个子序列是合法的括号序列。 举个例子，序列 "((())())(" 中，有八个这样的子序列："((())())"、"(())()"、"((()))"、"(()())"、"(())"、"()()"、"()" 以及空串 ""。

$1 \le |s| \le 300$。