Problem:


Score : 100 points

Problem Statement

Let N be a positive integer.
You are given a string s of length N - 1, consisting of < and >.

Find the number of permutations (p_1, p_2, \ldots, p_N) of (1, 2, \ldots, N) that satisfy the following condition, modulo 10^9 + 7:

For each i (1 \leq i \leq N - 1), p_i < p_{i + 1} if the i-th character in s is <, and p_i > p_{i + 1} if the i-th character in s is >.

Constraints

N is an integer.

2 \leq N \leq 3000

s is a string of length N - 1.

s consists of < and >.

Input

Input is given from Standard Input in the following format:

N
s

Output

Print the number of permutations that satisfy the condition, modulo 10^9 + 7.

Sample Input 1

4
<><

Sample Output 1

5

There are five permutations that satisfy the condition, as follows:

(1, 3, 2, 4)

(1, 4, 2, 3)

(2, 3, 1, 4)

(2, 4, 1, 3)

(3, 4, 1, 2)

Sample Input 2

5
<<<<

Sample Output 2

1

There is one permutation that satisfies the condition, as follows:

(1, 2, 3, 4, 5)

Sample Input 3

20
>>>><>>><>><>>><<>>

Sample Output 3

217136290

Be sure to print the number modulo 10^9 + 7.



Sample input:
4
<><


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solve(N, lessthan):
    k = 1
    table = [0] * (k + 1)
    if lessthan[-1]:
        for i in range(k + 1):
            table[i] = k - i
    else:
        for i in range(k + 1):
            table[i] = i

    for k in range(2, N):
        newtable = [0] * (k + 1)
        if lessthan[-k]:
            for i in range(k + 1):
                for j in range(k - i):
                    newtable[i] += table[j + i]
        else:
            for i in range(k + 1):
                for j in range(i):
                    newtable[i] += table[j]
        table = [x % MOD for x in newtable]
    return sum(table) % MOD


def main():
    # parse input
    N = int(input())
    lessthan = [c == ord("<") for c in input().strip()]
    print(solve(N, lessthan))


# tests
T0 = """
2
>
"""


def test_T0():
    """
    >>> as_input(T0)
    >>> main()
    1
    """


T01 = """
3
<<
"""


def test_T01():
    """
    >>> as_input(T01)
    >>> main()
    1
    """


T02 = """
3
>>
"""


def test_T02():
    """
    >>> as_input(T02)
    >>> main()
    1
    """


T03 = """
3
<>
"""


def test_T03():
    """
    >>> as_input(T03)
    >>> main()
    2
    """


T1 = """
4
<><
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5
    """


T2 = """
5
<<<<
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    1
    """


T3 = """
20
>>>><>>><>><>>><<>>
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    217136290
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
MOD = 10**9+7
n = int(input())
S = input()
dp = [1]*n
for s in S:
  if s == "<":
    dp = list(accumulate(dp[::-1][:-1]))[::-1]
  else:
    dp = list(accumulate(dp[:-1]))
ans = dp[0]%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
n = int(input())
S = input()
def main():
  dp = [[0]*(n+1) for _ in range(n+1)]
  for j in range(n):
    dp[1][j] = 1
  for i, s in enumerate(S, 1):
    if s == "<":
      dp[i+1][n-(i+1)] = dp[i][n-i]
      for j in range(n-i-2, -1, -1):
        dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
        dp[i+1][j] %= MOD
    else:
      dp[i+1][0] = dp[i][0]
      for j in range(1, n-i):
        dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
        dp[i+1][j] %= MOD
  ans = dp[n][0]
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
n = int(input())
S = input()
dp = [[0]*(n+1) for _ in range(n+1)]
for j in range(n):
  dp[1][j] = 1
for i, s in enumerate(S, 1):
  if s == "<":
    dp[i+1][n-(i+1)] = dp[i][n-i]
    for j in range(n-i-2, -1, -1):
      dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
      dp[i+1][j] %= MOD
  else:
    dp[i+1][0] = dp[i][0]
    for j in range(1, n-i):
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
      dp[i+1][j] %= MOD
ans = dp[n][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

N = int(input())
s = input()

# dp[i][j] := i 番目まで決めて i 番目の数より大きいものが j 個のときの場合の数
dp = [[0]*N for _ in range(N)]
dp[0] = [1]*(N+1)
for i in range(N-1):
    # 累積和をとっておく
    # for j in range(N-1):
    #     dp[i][j+1] += dp[i][j]
    for j in range(N-i-1):
        if s[i] == '<':
            for k in range(j+1, N-i):
                dp[i+1][j] += dp[i][k]
        else:
            for k in range(j+1):
                dp[i+1][j] += dp[i][k]
        dp[i+1][j] %= MOD

print(dp[N-1][0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
dp = [1] * n
mod = 10 ** 9 + 7
for ind, i in enumerate(s):
    dp2 = [0] * n
    if i == ">":
        s = 0
        for j in reversed(range(n-ind)):
            dp2[j] = s
            s += dp[j]
            s %= mod
    else:
        s = 0
        for j in range(n):
            s += dp[j]
            dp2[j] = s
            s %= mod
    dp = dp2
print(dp[0])
a = 0

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from itertools import accumulate
def resolve():
    n = int(input())
    # dp[i][j] : i まで見て末尾が j のもの (i <= j)
    dp = [0] * n
    dp[0] = 1
    for i, c in enumerate(input(), 1):
        S = list(accumulate([0] + dp))
        dp = [0] * n
        if c == '<':
            # ndp[j] = dp[0] + ... + dp[j - 1] # j <= i
            for j in range(i + 1):
                dp[j] = S[j]
        elif c == '>':
            # ndp[j] = dp[j] + ... + dp[i - 1] # j <= i
            for j in range(i + 1):
                dp[j] = S[i] - S[j]

    print(sum(dp) % MOD)
resolve()

Submission status: Time Limit Exceeded

Solution code:
def f(s):
  n=len(s)+1
  mod=pow(10,9)+7
  z=[[0]*n for _ in xrange(n)]
  z[0][0]=1
  for i in xrange(n-1):
    for j in xrange(n-1):
      z[i][j+1]+=z[i][j]
    for j in xrange(i+2):
      if s[i]=='>':
        z[i+1][j]=z[i][i]-(0 if j==0 else z[i][j-1])
      else:
        z[i+1][j]=(0 if j==0 else z[i][j-1])
  return sum(z[-1])%mod
input()
print f(raw_input().strip())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = input()
p = 10**9+7
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for j in range(n):
    DP[1][j] = 1
for i in range(2, n+1):
    A = [0]
    for j in range(n):
        A.append(A[-1]+DP[i-1][j])
    for j in range(n-i+1):
        if S[i-2] == '<':
            DP[i][j] = (A[n-(i-1)+1]-A[j+1]) % p
        else:
            DP[i][j] = A[j+1] % p
print(DP[n][0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
M = 10**9 + 7

def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[1] * n + [0] for _ in range(2)]
for i in reversed(range(n - 1)):
    for j in range(n - 1):
        dp[1][j + 1] = mod(dp[1][j + 1] + dp[1][j])
        dp[0][j] = dp[1][j]
    dp[0][-2] = dp[1][-2]
    # print(dp[0])

    for zk in range(n):
        cnt = 0

        if s[i] == "<":
            cnt = dp[0][zk - 1]
        else:
            zj = n - i - zk - 1
            cnt = dp[0][zk + zj - 1] - dp[0][zk - 1]
        dp[1][zk] = cnt

print(sum(dp[1]) % M)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
M = 10**9 + 7

def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[None] * n for _ in range(n)]
def dfs(zk, i=0):
    if dp[zk][i] is not None:
        return dp[zk][i]

    if i == n - 1:
        dp[zk][i] = 1
        return 1

    zj = n - i - zk - 1
    cnt = 0

    if s[i] == "<":
        for v in range(zk):
            cnt += dfs(v, i + 1)
    else:
        for v in range(zj):
            cnt += dfs(zk + v, i + 1)
    dp[zk][i] = cnt
    return cnt

def cumsum(array):
    array = array[:]
    for i in range(len(array) - 1):
        array[i + 1] = mod(array[i + 1] + array[i])
    array.append(0)
    return array

for i in reversed(range(n)):
    for zk in range(n):
        if i == n - 1:
            dp[i][zk] = 1
            continue

        zj = n - i - zk - 1
        cnt = 0

        if s[i] == "<":
            # for v in range(zk):
            #     # cnt = mod(cnt + dp[i + 1][v])
            cnt = cs[zk - 1]
        else:
            # for v in range(zj):
            #     # cnt = mod(cnt + dp[i + 1][zk + v])
            cnt = cs[zk + zj - 1] - cs[zk - 1]
        dp[i][zk] = cnt
    cs = cumsum(dp[i])

print(sum(dp[0]) % M)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
M = 10**9 + 7

dp = [[None] * n for _ in range(n)]
def dfs(zk, i=0):
    if dp[zk][i] is not None:
        return dp[zk][i]

    if i == n - 1:
        dp[zk][i] = 1
        return 1

    zj = n - i - zk - 1
    cnt = 0

    if s[i] == "<":
        for v in range(zk):
            cnt += dfs(v, i + 1)
    else:
        for v in range(zj):
            cnt += dfs(zk + v, i + 1)
    dp[zk][i] = cnt
    return cnt

def mod(v):
    if v >= M:
        return v % M
    return v

def cumsum(array):
    array = array[:]
    for i in range(len(array) - 1):
        array[i + 1] = mod(array[i + 1] + array[i])
    return array + [0]

for i in reversed(range(n)):
    for zk in range(n):
        if i == n - 1:
            dp[i][zk] = 1
            continue

        zj = n - i - zk - 1
        cnt = 0

        if s[i] == "<":
            for v in range(zk):
                # cnt = mod(cnt + dp[i + 1][v])
                cnt = cs[v]
        else:
            for v in range(zj):
                # cnt = mod(cnt + dp[i + 1][zk + v])
                cnt = cs[zk + zj - 1] - cs[zk - 1]
        dp[i][zk] = cnt
    cs = cumsum(dp[i])

# for i in range(n):
#     print(dfs(i))
# print(sum(dfs(i) for i in range(n - 1)) % M)
print(sum(dp[0]) % M)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
M = 10**9 + 7

dp = [[None] * n for _ in range(n)]
def dfs(zk, i=0):
    if dp[zk][i] is not None:
        return dp[zk][i]

    if i == n - 1:
        dp[zk][i] = 1
        return 1

    zj = n - i - zk - 1
    cnt = 0

    if s[i] == "<":
        for v in range(zk):
            cnt += dfs(v, i + 1)
    else:
        for v in range(zj):
            cnt += dfs(zk + v, i + 1)
    dp[zk][i] = cnt
    return cnt

def mod(v):
    if v >= M:
        return v % M
    return v

for zk in range(n):
    for i in reversed(range(n)):
        if i == n - 1:
            dp[zk][i] = 1
            continue

        zj = n - i - zk - 1
        cnt = 0

        if s[i] == "<":
            for v in range(zk):
                cnt = mod(cnt + dfs(v, i + 1))
        else:
            for v in range(zj):
                cnt = mod(cnt + dfs(zk + v, i + 1))
        dp[zk][i] = cnt

# for i in range(n):
#     print(dfs(i))
# print(sum(dfs(i) for i in range(n - 1)) % M)
print(sum([dp[v][0] for v in range(n)]) % M)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
MOD = 10**9 + 7

# dp[j] (i番目のiteration時点): 
#   左から(i+1)番目まで並べ終えたときに、最も右の数が、
#   そのときに残っている(N-i)個の数の中で(j+1)番目に小さい数である場合の数
dp = [1] * N
cum = [[i for i in range(1, N+1)], [0]*N]

for i in range(1, N):
  idx = i%2
  if S[i-1] == '<':
    for j in range(N-i):
      dp[j] = cum[idx-1][j]
      if j == 0:
        cum[idx][0] = dp[j]
      else:
        cum[idx][j] = (cum[idx][j-1] + dp[j]) % MOD
  
  else:
    for j in range(N-i):
      dp[j] = (cum[idx-1][N-i] - cum[idx-1][j]) % MOD
      if j == 0:
        cum[idx][0] = dp[j]
      else:
        cum[idx][j] = (cum[idx][j-1] + dp[j]) % MOD

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
s = input().rstrip()

dp = [[0] * n for _ in range(n)]
dp[0] = [1] * n

used = 0
for i, ch in enumerate(s):
    if ch == "<":
        for j in range(n - used - 1, -1, -1):
            if j-1 >= 0:
                dp[i+1][j-1] = dp[i][j]
        for j in range(n - 1, 0, -1):
            dp[i+1][j-1] += dp[i+1][j]
            dp[i+1][j-1] %= MOD
    else:
        for j in range(n - used - 2, -1, -1):
            dp[i+1][j] = dp[i][j]
        for j in range(1, n - used - 1):
            dp[i+1][j] += dp[i+1][j-1]
            dp[i+1][j] %= MOD
    used += 1

# for line in dp:
#     print(line)
print(sum(dp[-1]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
import numpy as np
MOD = 1000000007  # type: int


def solve(N: int, s: str):

    # DP[i][j]はi文字目までをみたす順列のうち、最後がjで終わるものの個数
    DP = np.zeros((N, N+1), dtype=np.int64)
    # DP = [[0]*(N+1) for _ in range(N)]
    DP[0][1] = 1

    for i in range(1, N):
        acc = list(accumulate(DP[i-1]))
        for j in range(1, (i+1)+1):
            if s[i-1] == "<":
                DP[i][j] = acc[j-1]
            else:
                DP[i][j] = acc[i+1] - acc[j-1]
            DP[i][j] %= MOD

    print(sum(DP[N-1]) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = next(tokens)  # type: str
    solve(N, s)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, s: str):

    # DP[i][j]はi文字目までをみたす順列のうち、最後がjで終わるものの個数
    DP = [[0]*(N+1) for _ in range(N)]
    DP[0][1] = 1

    for i in range(1, N):
        tot = 0
        acc = list(accumulate(DP[i-1]))
        for j in range(1, (i+1)+1):
            if s[i-1] == "<":
                DP[i][j] = acc[j-1]
            else:
                DP[i][j] = acc[i+1] - acc[j-1]
            DP[i][j] %= MOD

    print(sum(DP[N-1]) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = next(tokens)  # type: str
    solve(N, s)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = int(input())
s = input()

def main():
    md=10**9+7
    dp=[[0]*(n+1) for _ in range(n+1)]
    dp[1][0]=1
    dpx=dp[1]
    for x in range(2,n+1):
        dpx1=dpx
        dpx=dp[x]
        for i in range(x):
            if s[n-x]=="<":
                dpx[i]=sum(dpx1[i:x-1])%md
            else:
                dpx[i]=sum(dpx1[:i])%md
    #p2D(dp)
    print(sum(dp[n])%md)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = int(input())
s = input()

def main():
    md=10**9+7
    dp=[[0]*(n+1) for _ in range(n+1)]
    dp[1][0]=1
    dpx=dp[1]
    for x in range(2,n+1):
        dpx1=dpx
        dpx=dp[x]
        for i in range(x):
            dp_value=0
            if s[n-x]=="<":
                for j in range(i,x-1):
                    dp_value+=dpx1[j]
            else:
                for j in range(i):
                    dp_value+=dpx1[j]
            dpx[i]=dp_value%md
    #p2D(dp)
    print(sum(dp[n])%md)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = int(input())
s = input()
# combinationの準備
md = 10 ** 9 + 7
n_max = 3005
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

def com(com_n, com_r):
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

def main():
    sn=len(s)
    dp=[[1]*sn for _ in range(sn)]
    for w in range(1,sn):
        for l in range(sn-w):
            value=0
            if s[l]=="<":value+=dp[l+1][l+w]
            if s[l+w]==">":value+=dp[l][l+w-1]
            for i in range(l,l+w):
                if s[i]==">" and s[i+1]=="<":
                    value+=dp[l][max(i-1,l)]*dp[min(i+2,l+w)][l+w]*com(w+1,i-l+1)
            dp[l][l+w]=value%md
    #p2D(dp)
    print(dp[0][-1])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = int(input())
s = input()
# combinationの準備
md = 10 ** 9 + 7
n_max = 3005
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

def com(com_n, com_r):
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

def way(a):
    an = len(a)
    if an <= 1: return 1
    if a in memo: return memo[a]
    res = 0
    if a[0]: res += way(a[1:])
    if not a[-1]: res += way(a[:-1])
    for i in range(an - 1):
        if not a[i] and a[i + 1]:
            res += way(a[:i]) * way(a[i + 2:]) * com(an, i + 1)
    res %= md
    memo[a] = res
    return res
memo = {}

def main():
    a = [c == "<" for c in s]
    a=tuple(a)
    print(way(a))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = int(input())
s = input()
# combinationの準備
md = 10 ** 9 + 7
n_max = 3005
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

def com(com_n, com_r):
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

def way(s):
    sn = len(s)
    if sn <= 1: return 1
    if s in memo: return memo[s]
    res = 0
    if s[0] == "<": res += way(s[1:])
    if s[-1] == ">": res += way(s[:-1])
    for i in range(sn - 1):
        if s[i] == ">" and s[i + 1] == "<":
            res += way(s[:i]) * way(s[i + 2:]) * com(sn, i + 1)
    res %= md
    memo[s] = res
    return res
memo = {}

def main():
    print(way(s))

main()

Submission status: Time Limit Exceeded

Solution code:
temp=1
MOD=10**9+7
fact=[1]
infact=[1]
for i in range(1,5000):
    temp*=i
    temp%=MOD
    fact+=[temp]
    infact+=[pow(temp,MOD-2,MOD)]
def binomial(a,b):
    up=fact[a]
    down=(infact[a-b]*infact[b])%MOD
    return (up*down)%MOD


def find(s):
    N=len(s)+1
    dp=[[0 for i in range(N)] for j in range(N)]
    for length in range(1,N+1):
        if length==1:
            for start in range(0,N):
                dp[start][start]=1
            continue
        if length==2:
            for start in range(0,N-1):
                dp[start][start+1]=1
            continue            
        for start in range(0,N):
            left=start
            right=start+length-1
            if right>N-1:
                break
            if s[left]==">":
                dp[left][right]+=dp[left+1][right]
                dp[left][right]%=MOD
            if s[right-1]=="<":
                dp[left][right]+=dp[left][right-1]
                dp[left][right]%=MOD
            for j in range(left,right-1):
                if s[j]=="<" and s[j+1]==">":
                    need=j+1
                    dp[left][right]+=(binomial(length-1,need-left)*dp[left][need-1]*dp[need+1][right])%MOD
                    dp[left][right]%=MOD
    #print(dp)
    return dp[0][N-1]%MOD

                    
N=int(input())
s=input()
print(find(s))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

SIZE=10000; MOD=10**9+7 #ここを変更する

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

import sys
sys.setrecursionlimit(10**7)

n=int(input())
s=input()


memo = [[0]*(i+1) for i in range(n+1)]
 
def dp(r,l):
    if r-l<=2:
        memo[r][l] = 1
        return 1
    if memo[r][l] > 0:
        return memo[r][l]
    
    res = 0
    pt = l
    now = "<"
    while pt <= r-1:
        if pt < r-1 and s[pt] == "<":
            now = "<"
        else:
            if now  == "<":
#                print(pt,r,l)
                res += dp(r,pt+1) * dp(pt,l) * choose(r-l-1, pt-l)
                res %= MOD
            now = ">"    
        pt += 1

    
    memo[r][l] = res
    return res
 
dp(n,0)
#print(memo)
print(memo[n][0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(N, s):
    MOD = int(1e9 + 7)
    dp = [[0] * N for _ in range(N)]
    for j in range(N):
        dp[0][j] = 1
    for i in range(1, N):
        csum = list(accum(dp[i - 1], lambda x, y: (x + y) % MOD))
        dpi = dp[i]
        csum_ = csum[N - i]
        i_ = i - 1
        for j in range(N - i):  # N-(i+1)+1 = N-i
            dpi[j] = csum[j] if s[i_] == ">" else (csum_ - csum[j] + MOD) % MOD
    return(dp[-1][0])

N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1
print(f(N, s))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(N, s):
    MOD = int(1e9 + 7)
    dp = [[0] * N for _ in range(N)]
    for j in range(N):
        dp[0][j] = 1
    for i in range(1, N):
        dpi = dp[i]
        csum = list(accum(dp[i - 1], lambda x, y: (x + y) % MOD))
        csum_ = csum[N - i]
        for j in range(N - i):  # N-(i+1)+1 = N-i
            if s[i - 1] == "<":
                dpi[j] = csum_ - csum[j]
            else: #s[i-1] == ">"
                dpi[j] = csum[j]
    return(dp[-1][0])

N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1
print(f(N, s))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(N, s):
    MOD = int(1e9 + 7)
    dp = [[0] * N for _ in range(N)]
    for j in range(N):
        dp[0][j] = 1
    for i in range(1, N):
        dpi = dp[i]
        csum = list(accum(dp[i - 1], lambda x, y: (x + y) % MOD))
        csum_ = csum[N - i]
        for j in range(N - i):  # N-(i+1)+1 = N-i
            if s[i - 1] == "<":
                dpi[j] = (csum_ - csum[j]) % MOD
            else: #s[i-1] == ">"
                dpi[j] = csum[j]
    return(dp[-1][0])

N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1
print(f(N, s))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(N, s):
    MOD = int(1e9 + 7)
    dp = [[0] * N for _ in range(N)]
    for j in range(N):
        dp[0][j] = 1
    for i in range(1, N):
        dpi = dp[i]
        # csum: Cumulative sum
        # csum[x] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][x]
        csum = list(accum(dp[i - 1], lambda x, y: (x + y) % MOD))
        csum_ = csum[N - i]
        for j in range(N - i):  # N-(i+1)+1 = N-i
            if s[i - 1] == "<":
                dpi[j] = (dpi[j] + csum_ - csum[j]) % MOD
            else: #s[i-1] == ">"
                dpi[j] = (dpi[j] + csum[j]) % MOD
    return(dp[-1][0])

N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1
print(f(N, s))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(N, s):
    MOD = int(1e9 + 7)
    dp = [[0] * N for _ in range(N)]
    for j in range(N):
        dp[0][j] = 1
    for i in range(1, N):
        # csum: Cumulative sum
        # csum[x] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][x]
        csum = list(accum(dp[i - 1], lambda x, y: (x + y) % MOD))
        for j in range(N - i):  # N-(i+1)+1 = N-i
            if s[i - 1] == "<":
                dp[i][j] = (dp[i][j] + csum[N - i] - csum[j]) % MOD
            else: #s[i-1] == ">"
                dp[i][j] = (dp[i][j] + csum[j]) % MOD
    return(dp[-1][0])


N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1

print(f(N, s))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

mod = 10**9 + 7

dp = [[0] * n for _ in range(n)]

for more in range(n):
    dp[0][more] = 1

for i in range(n-1):
    if s[i] == "<":
        cum = 0
        for more in reversed(range(n-1-i)):
            cum += dp[i][more+1]
            cum %= mod
            dp[i + 1][more] += cum
            dp[i + 1][more] %= mod
    else:
        cum = 0
        for more in range(n-1-i):
            cum += dp[i][more]
            cum %= mod
            dp[i+1][more] += cum
            dp[i+1][more] %= mod

print(dp[n-1][0])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
mod=10**9+7

#DP[i]#最後においた数の右にある残っている個数
rest=N-1
DP=[1]*(N)

for s in S:
    NDP=[0]*(N)
    if s=="<":
        for i in range(rest+1):
            if i>=1:
                NDP[i-1]=(DP[i]+NDP[i-1])%mod

        DP=NDP
        for i in range(N-2,-1,-1):
            DP[i]=(DP[i+1]+DP[i])%mod

    else:
        DP=[DP[rest-i] for i in range(N)]#左右逆にして考える

        #print(DP)
        for i in range(rest+1):
            if i>=1:
                NDP[i-1]=(DP[i]+NDP[i-1])%mod

        DP=NDP
        for i in range(N-2,-1,-1):
            DP[i]=(DP[i+1]+DP[i])%mod


        DP=[DP[rest-1-i] for i in range(N)]

    rest-=1
    #print(DP,rest)

print(DP[0])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
mod=10**9+7


#パスカルの三角形を使う方法.
Combi=[[] for i in range(N+1)]
Combi[0]=[1,0]

for i in range(1,N+1):
    Combi[i].append(1)
    for j in range(i):
        Combi[i].append((Combi[i-1][j]+Combi[i-1][j+1])%mod)
    Combi[i].append(0)

COMP=[2]

for i in range(1,N-1):
    if S[i]==S[i-1]:
        COMP[-1]+=1

    else:
        COMP.append(1)
L=len(COMP)

DP=[0]*(N+1)#上にある残りの個数
DP[N]=1
rest=N



for x in COMP:

    NDP=[0]*(N+1)
    for i in range(N+1):
        for j in range(i+x,N+1):
            NDP[i]+=DP[j]*Combi[j-i-1][x-1]%mod

    rest-=x
    DP=[NDP[rest-i] for i in range(N+1)]
    #print(DP,rest)
    

print(DP[0])

Submission status: Accepted

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())
def inp():
    return input()

N=10**9 +7
n=int(inp())
s=inp()
dp=[[0]*(n+1) for _ in range(n+1)]#base 1 indexing
dp[1][1]=1
for i in range(2,n+1):
    pref=[0]
    for t in range(1,i):
        pref.append((pref[-1]+dp[i-1][t])%N)
    for j in range(1,i+1):


        if s[i-2]==">":
            l=j
            r=i-1
        else:

            l=1
            r=j-1

        if l>r:
            continue
        dp[i][j]=((pref[r]-pref[l-1])%N + N)%N
ans=0
for i in range(1,n+1):
    ans=(ans+dp[n][i])%N

print(ans)

Submission status: Accepted

Solution code:
M=10**9+7;n=int(input());s=input();d=[1]*n
for k in range(n-1,0,-1):
 N=[0]*n
 for i in range(k+1):
  if'<'<s[n-1-k]:N[0]+=d[i];N[i]-=d[i]
  else:N[i]+=d[i];N[k]-=d[i]
 for i in range(k):N[i+1]=(N[i+1]+N[i])%M
 d=N
print(d[0]%M)