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 .

Solution (Python):


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

MOD = 10**9 + 7


dp = [[0]*N for _ in range(N)]
for i in range(N):
    dp[0][i] = 1 

for i in range(1,N):
    if s[i-1] == ">": 
        x = dp[i-1][N-i]
        for j in reversed(range(N-i)): 
            dp[i][j] += x
            dp[i][j] %= MOD
            x += dp[i-1][j]
            x %= MOD
    else: 
        x = dp[i-1][0]
        for j in range(N-i): 
            dp[i][j] += x
            dp[i][j] %= MOD
            x += dp[i-1][j+1]
            x %= MOD

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

Solution (Python):
N = int(input())
s = input()

MOD = 10**9 + 7


dp = [[0]*N for _ in range(N)]
for i in range(N):
    dp[0][i] = 1 

for i in range(1,N):
    if s[i-1] == ">": 
        x = dp[i-1][N-i]
        for j in reversed(range(N-i)): 
            dp[i][j] += x
            dp[i][j] %= MOD
            x += dp[i-1][j]
            x %= MOD
    else: 
        x = dp[i-1][0]
        for j in range(N-i): 
            dp[i][j] += x
            dp[i][j] %= MOD
            x += dp[i-1][j+1]
            x %= MOD

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

Solution (Python):
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])

Solution (Python):
N=int(input())
S=str(input())
P=10**9+7

DP=[[0]*(N+1) for _ in range(N+1)]

for index1 in range(N):
    DP[1][index1]=1

for i in range(2,N):
    
    C=[0]*(N+1)
    C[0]=DP[i-1][0]%P
    for index2 in range(1,N+1):
        C[index2]=(C[index2-1]+DP[i-1][index2])%P
    for j in range(N-i+1):
        if S[i-2]=='>':
            DP[i][j]=(C[N-i+1]-C[j])%P
        else:
            DP[i][j]=C[j]

if S[N-2]=='>':
    DP[N][0]=DP[N-1][1]
else:
    DP[N][0]=DP[N-1][0]

print(DP[N][0]%P)

Solution (Python):
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])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    s = input()
    MOD = 10 ** 9 + 7
    
    dp = [[0] * N for _ in range(N)]
    acc = [i for i in range(1, N + 1)]
    
    for i in range(1, N):
        for j in range(N - i + 1):
            if s[i - 1] == '<':
                dp[i][j] = (acc[N - i] - acc[j]) % MOD
            else:
                dp[i][j] = acc[j]
        acc[0] = dp[i][0]
        for j in range(1, N):
            acc[j] = (acc[j - 1] + dp[i][j]) % MOD
    print(dp[-1][0])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    s = input()
    MOD = 10 ** 9 + 7
    
    dp = [[0] * N for _ in range(N)]
    for i in range(N):
        dp[0][i] = 1
    acc = [i for i in range(1, N + 1)]
    
    for i in range(1, N):
        for j in range(N - i + 1):
            if s[i - 1] == '<':
                dp[i][j] = (acc[N - i] - acc[j]) % MOD
            else:
                dp[i][j] = acc[j]
        acc[0] = dp[i][0]
        for j in range(1, N):
            acc[j] = (acc[j - 1] + dp[i][j]) % MOD
    print(dp[-1][0])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    s = input()
    MOD = 10 ** 9 + 7
    
    dp = [[0] * N for _ in range(N)]
    for i in range(N):
        dp[0][i] = 1
    acc = [i for i in range(1, N + 1)]
    
    for i in range(1, N):
        for j in range(N - i + 1):
            if s[i - 1] == '<':
                dp[i][j] = (acc[N - i] - acc[j]) % MOD
            else:
                dp[i][j] = acc[j]
        acc[0] = dp[i][0]
        for j in range(1, N):
            acc[j] = (acc[j - 1] + dp[i][j]) % MOD
    print(dp[-1][0])


if __name__ == '__main__':
    solve()

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    s="<"+input()
    
    dp=[[0]*(N+1)for _ in range(N+1)]
    
    dp[0][-1]=1
    
    for i in range(N):
        if s[i]==">":
            S=0
            for j in range(N-i+1):
                S=(S+dp[i][j])%mod
                dp[i+1][j]=S
        else:
            S=0
            for j in range(N-i,0,-1):
                S=(S+dp[i][j])%mod
                dp[i+1][j-1]=S
    print(dp[-1][0])
                
                
                    
            

main()

Solution (Python):
import sys


def main():
    N = int(input())
    s = input()
    MOD = 10**9+7
    base = [1]*N
    
    for i in range(N-1):
        imos = [0]*N
        if s[i] == "<":
            for j in range(N-i-1):
                imos[0] += base[1+j]
                imos[1+j] -= base[1+j]
        else:
            for j in range(N-i-1):
                imos[j] += base[j]
                imos[N-i-1] -= base[j]
        for k in range(N-1):
            imos[k+1] += imos[k]
            imos[k+1] %= MOD
        base = imos
    
    print(base[0]%MOD)
    
if __name__ == "__main__":
    main()

Solution (Python):
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)]
s = [v == "<" for v in s]
for i in reversed(range(n - 1)):
    for j in range(n - 1):
        dp[1][j + 1] = dp[1][j + 1] + dp[1][j]
        dp[0][j] = dp[1][j]
    dp[0][-2] = dp[1][-2]

    for zk in range(n - i):
        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] = mod(cnt)

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

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
mod = 10 ** 9 + 7
dp = [[0] * N for _ in range(N)]
for j in range(N): dp[0][j] = 1

for i in range(N - 1):
  if S[i] == "<":
    for j in range(N - i - 1):
      dp[i + 1][j] += dp[i][j]
      dp[i + 1][j] %= mod
    for j in range(N - i - 2):
      dp[i + 1][j + 1] += dp[i + 1][j]
      dp[i + 1][j + 1] %= mod
  else:
    for j in range(1, N - i):
      dp[i + 1][j - 1] += dp[i][j]
      dp[i + 1][j - 1] %= mod
    for j in range(N - 1, 0, -1):
      dp[i + 1][j - 1] += dp[i + 1][j]
      dp[i + 1][j - 1] %= mod
print(dp[-1][0])

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
s = list(input())
mod = 10**9+7


dp = [[0]*n for i in range(n)]
for i in range(n):
    dp[0][i] = 1
pre_cum = list(range(1,n+1))

for i in range(1,n):
    for j in range(n-i+1):
        if s[i-1] == "<":
            dp[i][j] = (pre_cum[n-i]-pre_cum[j])%mod
        else:
            dp[i][j] = pre_cum[j]
    c = 0
    for j in range(n):
        c = (c+dp[i][j])%mod
        pre_cum[j] = c
print(dp[-1][0]%mod)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
S = input()
dp = [[0]*(n+1) for i in range(n)]


for j in range(n):
  dp[0][j] = 1
for i in range(n-1):
  acum = [0]*(n+1)
  for j in range(n):
    acum[j+1] = acum[j] + dp[i][j]
  for j in range(n-i-1):
    if S[i] == "<":
      dp[i+1][j] = (acum[n]-acum[j+1]) % mod
    else:
      dp[i+1][j] = (acum[j+1] - acum[0]) % mod
print(dp[n-1][0])

Solution (Python):
mod = 10**9+7

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

dp = [1]*n
for i in range(n-1):
    nxt = [0]*(n+1)
    
    
    
    
    
    
    
    for j in range(n-i):
        if s[i] == "<":
            left = j
            right = n-1-i
        else:
            left = 0
            right = j
        if left >= right:
            continue
        nxt[left] += dp[j]
        nxt[right] -= dp[j]
    for j in range(n):
        nxt[j+1] += nxt[j]
        nxt[j+1] %= mod
    dp = nxt
ans = sum(dp)%mod
print(ans)

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




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])

Solution (Python):
import numpy as np
n=int(input())
s=list(input())
dp=np.ones(1,dtype=np.int64)
mod=10**9+7
for c in s:
    d=np.zeros(len(dp)+1,dtype=np.int64)
    if c=='<':
        d[1:]=dp.cumsum(dtype=np.int64)%mod
    else:
        d[:-1]=np.cumsum(dp[::-1],dtype=np.int64)[::-1]%mod
    dp=d
print(sum(dp)%mod)

Solution (Python):
N = int(input())
s = input()

MOD = 10**9 + 7

dp =  [[0] * N for i in range(N)]

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

ans = sum(dp[N-1]) % MOD
print(ans)

Solution (Python):
N = int(input())
s = input()

mod = 10**9+7
dp = [[0]*N for _ in range(N)]
t = [1]*N
if s[0] == "<":
    t[0] = 0
else:
    t[N-1] = 0
dp[0] = t

S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i] + dp[0][i]
     
for i in range(N-1):
    if s[i] == "<":
        for j in range(N-1):
            dp[i+1][j] = S[N] - S[j+1]
    else:
        for j in range(N):
            if i+j+1 < N:
                dp[i+1][j] = S[j+1]
                
    S = [0]*(N+1)
    for j in range(N):
        dp[i+1][j] %= mod
        S[j+1] = S[j] + dp[i+1][j]
        S[j+1] %= mod
        
print(dp[N-1][0])

Solution (Python):

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



print(sum(dp[-1]) % MOD)

Solution (Python):
N, = map(int, input().split())
M = 10**9+7
s = input().strip()
dp = [[0]*N for _ in range(N)]
for i in range(N):
    dp[0][i] = 1
ss = N
for i, c in enumerate(s):
    bs = 0
    if c == ">":
        for j in range(N-i):
            ss -= dp[i][j]
            dp[i+1][j] = ss%M

            bs = (bs+ss)%M
    else:
        ss = 0
        for j in range(N-i-1):
            ss += dp[i][j]
            dp[i+1][j] = ss%M
            bs = (bs+ss)%M

    ss = bs%M
print(dp[-1][0]%M)

Solution (Python):

import sys
import numpy as np
MOD = 1000000007  


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

    
    DP = np.zeros(N+1, dtype=np.int64)
    DP[1] = 1

    for i in range(1, N):
        acc = np.cumsum(DP)
        if s[i-1] == "<":
            DP[1:i+2] = np.mod(acc[:i+1], MOD)
        else:
            DP[1:i+2] = np.mod(acc[i+1]-acc[:i+1], MOD)

    print(np.mod(DP.sum(), 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))  
    s = next(tokens)  
    solve(N, s)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from itertools import accumulate
import numpy as np
MOD = 1000000007  


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

    
    DP = np.zeros((N, N+1), dtype=np.int64)
    DP[0][1] = 1

    for i in range(1, N):
        acc = np.cumsum(DP[i-1])
        if s[i-1] == "<":
            DP[i][1:i+2] = np.mod(acc[:i+1], MOD)
        else:
            DP[i][1:i+2] = np.mod(acc[i+1]-acc[:i+1], MOD)

    print(np.mod(DP[N-1].sum(), 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))  
    s = next(tokens)  
    solve(N, s)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from itertools import accumulate
INF = float("inf")

MOD = 1000000007  


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

    
    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))  
    s = next(tokens)  
    solve(N, s)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
n=int(input())
s=input()
a=np.ones(n)
m=10**9+7
for i in s:
    if i=="<":
        a=a[:-1].cumsum()
    else:
        a=a[1:][::-1].cumsum()[::-1]
    a%=m
print(int(a[0]))

Solution (Python):
n = int(input())
s = input()
MOD = 10**9 + 7

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

for i in range(n - 1):
    ruiseki = [0] * (n + 1)
    for j in range(n):
        ruiseki[j+1] = ruiseki[j] + dp[i][j]
        ruiseki[j+1] %= MOD

    if s[i] == "<":
        for j in range(n-i-1):
            dp[i+1][j] += ruiseki[n] - ruiseki[j+1]
            dp[i+1][j] %= MOD

    if s[i] == ">":
        for j in range(n-i-1):
            dp[i+1][j] += ruiseki[j+1]
            dp[i+1][j] %= MOD

print(dp[-1][0] % MOD)

Solution (Python):
MOD = 10**9+7
n = int(input())
s = input()
dp = [[0] * (n + 1) for _ in range(n + 1)]

dp[1][1] = 1
for length in range(2, n + 1):
    pref = [0] * (length + 1)
    for i in range(1, length):
        pref[i] = (pref[i - 1] + dp[length - 1][i]) % MOD
    for b in range(1, length + 1):
        l = r = 0
        if s[length - 2] == '<':
            l, r = 1, b - 1
        else:
            l, r = b, length - 1
        if l <= r:
            dp[length][b] = (dp[length][b] + (pref[r] - pref[l - 1] + MOD) % MOD) % MOD
res = sum(dp[n]) % MOD
print(res)

Solution (Python):
N = int(input())
S = input()
P = 10**9+7
X = [1] * N
for i in range(N-1):
    Y = [0] * (N-1-i)
    if S[i] == "<":
        Y[0] = X[0]
        for i in range(1, N-1-i):
            Y[i] = (Y[i-1] + X[i]) % P
    else:
        Y[N-2-i] = X[N-1-i]
        for i in range(N-2-i)[::-1]:
            Y[i] = (Y[i+1] + X[i+1]) % P
    X = Y

print(X[0])

Solution (Python):
N = int(input())
s = input()
mod = 10**9+7

dp = [[0] * N for _ in range(N)]
dp[0][0] = 1
for i in range(N-1):
    prev_cs = [0] * (N+1)
    for j in range(N):
        prev_cs[j+1] = (prev_cs[j] + dp[i][j]) % mod
    if s[i] == '>':
        for j in range(i+2):
            dp[i+1][j] = (prev_cs[-1] - prev_cs[j]) % mod
    else:
        for j in range(i+2):
            dp[i+1][j] = prev_cs[j]

ans = 0
for x in dp[-1]:
    ans = (ans + x) % mod
print(ans)

Solution (Python):
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]
        if s[n - x] == "<":
            for i in range(x-2,-1,-1):
                dpx[i]=(dpx[i+1]+dpx1[i])%md
        else:
            for i in range(1,x):
                dpx[i]=(dpx[i-1]+dpx1[i-1])%md
    
    print(sum(dp[n])%md)

main()

Solution (Python):
mod = 10**9+7
N = int(input())
s = input()
dp = [[0]*N for _ in range(N)]
for i in range(N):
    dp[0][i] = 1
for i in range(1, N):
    if s[i-1] == '>':
        dp[i][0] = dp[i-1][0]
        for j in range(1, N-i):
            dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod
    else:
        for j in range(N-1)[::-1]:
            dp[i][j] = (dp[i][j+1]+dp[i-1][j+1])%mod
print(sum(dp[-1])%mod)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
S = read().rstrip().decode('utf-8')

MOD = 10**9 + 7

"""
・最後に使った数に対して、下側に残っている個数 -> 数え上げ
"""

dp = np.ones(N,np.int64) 

for s in S:
    prev = dp
    if s == '<':
        
        dp = prev[:-1].cumsum()
    else:
        
        dp = prev[1:][::-1].cumsum()[::-1]
    dp %= MOD

answer = dp[0]
print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    s=input()
    dp=[1]*n
    for i in range(1,n):
        ndp=[0]*n
        S=[0]*(n+1)
        for j in range(n):
            S[j+1]=S[j]+dp[j]
        for less in range(n-i):
            if(s[i-1]=='<'): ndp[less]=S[less+1]
            else: ndp[less]=S[n]-S[less+1]
            ndp[less]%=MOD
        dp=ndp
    print(dp[0])
resolve()

Solution (Python):

from  itertools import accumulate
mod=1000000007
n=int(input())
s=input()
dp=[1]*n
for i in range(n-1):
    if s[i]==">":
        dp.reverse()
        dp=list(accumulate(dp[:-1]))
        dp.reverse()
    else:
        dp=list(accumulate(dp[:-1]))
    for j in range(len(dp)):
        dp[j]%=mod
print(dp[0])

Solution (Python):
MOD = 10**9+7
n = int(input())
s = input()
dp = [[0 for _ in range(n)] for _ in range(n)]
dp[0] = [1 for _ in range(n)]

def cum_get(lis, l, r):
	if l > r:
		return 0
	else:
		return (lis[r+1] - lis[l]) % MOD

for i in range(n-1):
	cum = [0]
	for j in range(n):
		cum.append(cum[-1] + dp[i][j])
	if s[i] == "<":
		for j in range(n-i):
			dp[i+1][j] = cum_get(cum, 0, j)
	else:
		for j in range(n-i):
			dp[i+1][j] = cum_get(cum, j+1, n-i-1)

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

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9 + 7
N = int(input())
S = input().rstrip()

dp = np.ones(N,dtype=np.int64) 

for s in S:
    incr = dp.cumsum()[:-1] % MOD
    if s == '<':
        dp = incr
        continue
    decr = (dp.sum() - incr) % MOD
    dp = decr

answer = dp[0]
print(answer)

Solution (Python):
N = int(input())
S = [1 if s == '<' else 0 for s in input().strip()]
mod = 10**9+7

dp = [1]*N + [0]

for j, s in enumerate(S):
    dp2 = [0]*(N+2)
    if s == 1:
        for i, d in enumerate(dp):
            dp2[0] += d
            dp2[i] -= d
    else:
        for i, d in enumerate(dp):
            dp2[i] += d
            dp2[N-j-1] -= d
    dp2.pop()
    for i in range(1, N+1):
        dp2[i] = (dp2[i-1] + dp2[i]) % mod
    dp = dp2[:]
ans = 0
for d in dp:
    ans = (ans + d) % mod
print(ans)

Solution (Python):


n=int(input())
s=input()
MOD = 10**9+7

dp = [1]*n

for i,c in enumerate(s):
    if c == "<":
        ssum = sum(dp[1:n-i])
        ssum %= MOD
        for j in range(n-i-1):
            dp[j] = ssum
            ssum -= dp[j+1]
            ssum %= MOD

    else:
        ssum = dp[0]
        for j in range(n-i-1):
            dp[j] = ssum
            ssum += dp[j+1]
            ssum %= MOD




print(dp[0])

Solution (Python):
def f(n, s):
    md = 10 ** 9 + 7
    dp = [1] * n
    for i in range(n - 1):
        if s[i] == "<":
            L = dp[0]
            for dpi in range(1, n - i - 1):
                dp[dpi] = L = (dp[dpi] + L) % md
            dp = dp[:-1]
        else:
            R = dp[-1]
            for dpi in range(n - i - 2, 0, -1):
                dp[dpi] = R = (dp[dpi] + R) % md
            dp = dp[1:]
    print(dp[0])


n = int(input())
s = input()
f(n, s)

Solution (Python):
def f(n, s):
    md = 10 ** 9 + 7
    dp = [1] * n
    for i in range(n - 1):
        if s[i] == "<":
            L = dp[0]
            for dpi in range(1, n - i - 1):
                dp[dpi] = L = (dp[dpi] + L) % md
            dp = dp[:-1]
        else:
            R = dp[-1]
            for dpi in range(n - i - 2, 0, -1):
                dp[dpi] = R = (dp[dpi] + R) % md
            dp = dp[1:]
    print(dp[0])


n = int(input())
s = input()
f(n, s)

Solution (Python):
md = 10 ** 9 + 7
n = int(input())
s = input()
dp = [1] * n
for i in range(n - 1):
    if s[i] == "<":
        L = dp[0]
        for dpi in range(1, n - i - 1):
            dp[dpi] = L = (dp[dpi] + L) % md
        dp = dp[:-1]
    else:
        R = dp[-1]
        for dpi in range(n - i - 2, 0, -1):
            dp[dpi] = R = (dp[dpi] + R) % md
        dp = dp[1:]
print(dp[0])

Solution (Python):
md = 10 ** 9 + 7
n = int(input())
s = input()
dp = [1] * n
for i in range(n - 1):
    if s[i] == "<":
        for dpi in range(1, n - i - 1):
            dp[dpi] = (dp[dpi] + dp[dpi - 1]) % md
        dp = dp[:-1]
    else:
        for dpi in range(n - i - 2, 0, -1):
            dp[dpi] = (dp[dpi] + dp[dpi + 1]) % md
        dp = dp[1:]
print(dp[0])

Solution (Python):


import sys
input = sys.stdin.readline

def f2(N, s):
    MOD = int(1e9 + 7)
    dp = [1] * N
    for i in range(1, N):
        csum = list(dp)
        for j in range(1, N - i + 1):
            csum[j] += csum[j - 1]
            csum[j] %= MOD
        csum_ = csum[N - i]
        i_ = i - 1
        for j in range(N - i):  
            dp[j] = csum[j] if s[i_] == ">" else \
                (csum_ - csum[j] + MOD) % MOD
    return(dp[0])

N = int(input()) 
s = input().rstrip() 
print(f2(N, s))

Solution (Python):


import sys
input = sys.stdin.readline

def f2(N, s):
    MOD = int(1e9 + 7)
    dp = [1] * N
    for i in range(1, N):
        csum = list(dp)
        for j in range(1, N - i + 1):
            csum[j] += csum[j - 1]
        csum_ = csum[N - i]
        i_ = i - 1
        for j in range(N - i):  
            dp[j] = csum[j] if s[i_] == ">" else (csum_ - csum[j] + MOD) % MOD
    return(dp[0])

N = int(input()) 
s = input().rstrip() 
print(f2(N, s))

Solution (Python):
mod=10**9+7
n=int(input())
s=input()
DP=[[0]*n for _ in range(n)]
for j in range(n):
    DP[0][j]=1
for i in range(n-1):
    if s[i]=='<':
        acc=0
        for j in range(n-1-i)[::-1]:
            acc+=DP[i][j+1]
            acc%=mod
            DP[i+1][j]+=acc
            DP[i+1][j]%=mod
    else:
        acc=0
        for j in range(n-i-1):
            acc+=DP[i][j]
            acc%=mod
            DP[i+1][j]+=acc
            DP[i+1][j]%=mod
print(DP[n-1][0])

Solution (Python):
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])

Solution (Python):


MOD = 1000000007


n = input()
s = raw_input()

dp = [[0] * n for _ in range(n)]
dp[0][0] = 1
for i in range(1, n):
    if s[i - 1] == '<':
        for j in range(1, i + 1):
            dp[i][j] = (dp[i - 1][j - 1] + dp[i][j - 1]) %  MOD
    else:
        for j in range(i - 1, -1, -1):
            dp[i][j] = (dp[i - 1][j] + dp[i][j + 1]) %  MOD
print(sum(dp[n - 1]) % MOD)

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


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)]

        
        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[0])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    s = S()
    t = [1] * n
    for i in range(n-1):
        c = s[i]
        u = [None] * (n-i-1)
        a = 0
        if c == '>':
            for j in range(n-i-1-1,-1,-1):
                a += t[j+1]
                a %= mod
                u[j] = a
        else:
            for j in range(n-i-1):
                a += t[j]
                a %= mod
                u[j] = a

        t = u

    return u[0] % mod


print(main())

Solution (Python):
from itertools import accumulate

n = int(input())
s = input()
dp = [1] * n
MOD = 10 ** 9 + 7
for i in range(n - 1):
    if s[i] == '>':
        dp.reverse()
        dp = list(accumulate(dp[:-1]))
        dp.reverse()
    else:
        dp = list(accumulate(dp[:-1]))
    for j in range(len(dp)):
        dp[j] %= MOD
print(dp[0])

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

dp = [[0]*(N+1) for i in range(N+1)]
P = [0]*(N+1); Q = [0]*(N+1)
P[1] = 1
for i in range(N-2, 0, -1):
    r = 0
    if S[i-1] == '<':
        if S[i] == '<':
            for k in range(1, N-i+1):
                Q[k] = r = (r + P[k-1]) % MOD
        else:
            for k in range(1, N-i+1):
                Q[k] = r = (r + P[N-i-k]) % MOD
    else:
        if S[i] == '<':
            for k in range(1, N-i+1):
                Q[k] = r = (r + P[N-i-k]) % MOD
        else:
            for k in range(1, N-i+1):
                Q[k] = r = (r + P[k-1]) % MOD
    P, Q = Q, P
print(sum(P) % MOD)

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

dp = [[0]*(N+1) for i in range(N+1)]
P = [0]*(N+1); Q = [0]*(N+1)
P[1] = 1
for i in range(N-2, 0, -1):
    r = 0
    if S[i-1] == '<':
        if S[i] == '<':
            for k in range(1, N-i+1):
                Q[k] = r = (r + P[k-1]) % MOD
        else:
            for k in range(1, N-i+1):
                Q[k] = r = (r + P[N-i-k]) % MOD
    else:
        if S[i] == '<':
            for k in range(1, N-i+1):
                Q[k] = r = (r + P[N-i-k]) % MOD
        else:
            for k in range(1, N-i+1):
                Q[k] = r = (r + P[k-1]) % MOD
    P, Q = Q, P
print(sum(P) % MOD)