from itertools import accumulate from collections import defaultdict MOD = 998244353 N = int(input()) S = input() lparens = [] for c in S: v = 1 if c == '(' else -1 lparens.append(v) acc = list(accumulate(lparens)) ns = len(S) # dp = [[-1] * (ns+1) for _ in range(ns+1)] dp = defaultdict(int) # dp[0][0] = 1 dp[0, 0] = 1 for i, c in enumerate(S): #print(f'{i=}') # pp = [[0] * (ns+1) for _ in range(ns+1)] pp = defaultdict(int) dp, pp = pp, dp lpar = 0 if i > 0: lpar = acc[i-1] # 開きカッコの個数 if c == '(': # 赤を増やす for j in range(ns): k = lpar - j dp[j+1, k] += pp[j, k] dp[j+1, k] %= MOD # for k in range(ns): # dp[j+1][k] += pp[j][k] # dp[j+1][k] %= MOD dp[k, j+1] += pp[j, k] dp[k, j+1] %= MOD # for k in range(ns): # j = lpar - k # dp[j, k+1] += pp[j, k] # dp[j, k+1] %= MOD # # 青を増やす # for j in range(ns): # k = lpar - j # dp[j][k+1] += pp[j][k] # dp[j][k+1] %= MOD # # for k in range(ns): # # dp[j][k+1] += pp[j][k] # # dp[j][k+1] %= MOD elif c == ')': # 赤を減らす for j in range(ns): k = lpar - j if j > 0: dp[j-1, k] += pp[j, k] dp[j-1, k] %= MOD # for k in range(ns): # if j == 0: continue # dp[j-1][k] += pp[j][k] # dp[j-1][k] %= MOD # 青を減らす for j in range(ns): k = lpar - j if k < 0: continue dp[j, k-1] += pp[j, k] dp[j, k-1] %= MOD # for k in range(ns): # if k == 0: continue # dp[j][k-1] += pp[j][k] # dp[j][k-1] %= MOD ans = dp[0, 0] print(ans)