← 返回题目列表

AtCoder · arc194_d

D. 反括号

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

字符串被定义为 有效的括号序列 当且仅当满足以下条件之一:

  • 这是一个空字符串。
  • 存在有效的括号序列 A 这样字符串是通过连接获得的 (, A,和 ) 按此顺序。
  • 存在非空有效括号序列 A 和 B 这样字符串是通过连接获得的 A 和 B 按此顺序。

为您提供了有效的括号序列 S 长度 N。您可以多次执行以下操作:

  • 选择一个连续的子字符串 S 是一个有效的括号序列,并将其反转。

这里,反转子串 S 来自 l- 第一个字符 r- 第一个字符含义如下:

  • 对于每个整数 i 满意 l \leq i \leq r,同时替换 S_i 与 ) if S_{l+r-i} is (,并与 ( if S_{l+r-i} is )。(注意这里的倒车与通常的倒车定义不同。)

求模数 998244353,不同的字符串 S 您可以在流程结束时获得。

约束

  • 1 \leq N \leq 5000
  • |S| = N
  • S 是有效的括号序列。

输入

输入由标准输入按以下格式给出:

N
S

输出

打印答案。


示例输入 1

6
(())()

示例输出 1

2

例如,您可以变换 S 进入 ()(()) 通过执行以下操作:

  • 选择第 1 到第 6 个字符的子字符串 S。这是一个有效的括号序列。 S 变为 ()(()).

唯一可以形成的其他字符串是 (())()。因此,答案是 2.


示例输入 2

2
()

示例输出 2

1