memg = {'': 1}
mod = 10**5


def f(s):
    if s[0] + s[-1] in ['()', '[]', '{}']:
        ans = 1
    elif s[0] in '({[' and s[-1] == '?':
        ans = 1
    elif s[0] == '?' and s[-1] in ')}]':
        ans = 1
    elif s[0] == s[-1] == '?':
        ans = 3
    else:
        return 0
    return (ans * g(s[1:-1])) % mod


def g(s):
    if not s in memg:
        memg[s] = sum(f(s[:k]) * g(s[k:])
                      for k in range(2, len(s) + 1, 2)) % mod
    return memg[s]

input()
print(g(input()))