小苯的括号计数

题号：NC280989
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小苯有一个括号串 $S$ （不一定合法），小苯又对回文串十分感兴趣，他很快就计算出了 $S$ 中有多少个连续子串是回文的。

但他觉得这个问题十分简单，于是他想要加大难度，现在他想知道： $S$ 中有多少个非空的连续子串是回文，并且合法的括号串。
（合法括号串是指：可以在其中插入数字和运算符，能构成合法的计算式的串，例如 "()", "()()", "(())" 都是合法串。）

他面对自己加强后的难题版本犯了难，于是想请你帮他算一算。

输入描述:

每个测试文件内都包含多组测试数据。
第一行一个正整数 ，表示测试数据的组数。
接下来对于每组测试数据，输入包含一行一个字符串 ，表示小苯的括号串 。
（保证  中仅含有 "(" 字符和 ")"字符。）
（保证同一文件的所有测试数据中， 的总和不超过 。）
（注意： 本身并不一定是合法的括号串。）

输出描述:

输出  行，每行一个整数表示合法的连续子串个数。
（由于答案可能很大，因此输出结果对  取模的值。）

示例1

输入

复制

1
(

输出

复制

说明

显然没有任何一个连续子串是合法的括号串。

备注:

合法括号串：
 首先空串是合法的括号串（但在本题中我们不考虑）
 如果串  合法，则  也合法， 也合法， 也合法。