Alice和Bob知道，一个由空格、左括号、右括号组成的序列被称为括号序列。有一类特殊的括号序列被称为“合法括号序列”。已经知道：
（1）“（）”是合法的括号序列，空串是合法的括号序列。
（2）如果 是合法的括号序列， 是合法的括号序列，则 与 拼接起来的序列 也是合法的括号序列。
（3）如果S是合法的括号序列，在其左右分别插入一个左括号和一个右括号所得到的字符串(++)也是合法的括号序列。
（4）如果 是合法的括号序列，在 的任何位置（包括头尾位置）插入一个空格，得到的序列也是合法的括号序列。
现在，Alice希望知道：对于某个已知的有限状态自动机中的状态 与 ，存在多少以 为起点， 为终点的长度为 的合法括号序列。
所谓有限状态自动机，又可以被认为是一个有向图 ，由 个结点组成，每一个结点表示一个状态，且存在三类以此为起点出去的有向边，对于每一个状态（或结点）来说其出去的同一类有向边将指向同样的状态（或结点）。三类有向边分别代表三种符号：左括号(，右括号)和空格。
这里，我们将状态（或结点）从 开始编号。对于第 个状态，用 分别表示从 出发，代表了左括号、右括号和空格的那一类边指向的状态（或结点），再用 表示每一类边的个数。
对于一条从 出发到 结束的路径，满足长度为 且路径经过的边对应的符号组成了一组合法的括号匹配，则称作“满足 的合法括号序列”。
现在，Alice为Bob提供了自动机 ，并提出 组询问。对于每一组询问，Alice会给出 ，她希望Bob可以告诉她满足 的合法括号序列有多少组。她只需要知道答案除以 后的余数。
