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: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    s=input()
    mod=10**9+7
    #i(1-)番目の数まで決めた時，それより小さな数がj個ある場合の数
    dp=[[0]*(n+1) for _ in range(n+1)] 
    for i in range(n):
        dp[1][i]=1
    cum=[0]*(n+1)
    for i in range(2,n+1):
        cum[0]=dp[i-1][0]
        for j in range(1,n-i+2):
            cum[j]=(cum[j-1]+dp[i-1][j])%mod
        if s[i-2]=="<":
            for j in range(n-i+1):
                dp[i][j]=(cum[j])%mod
        else:
            for j in range(n-i+1):
                dp[i][j]=(cum[n-i+1]-cum[j])%mod
    print(dp[n][0])
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    s=input()
    mod=10**9+7
    #i(1-)番目の数まで決めた時，それより大きな数がj個ある場合の数
    dp=[[0]*(n+1) for _ in range(n+1)] 
    for i in range(n):
        dp[1][i]=1
    cum=[0]*(n+1)
    for i in range(2,n+1):
        cum[0]=dp[i-1][0]
        for j in range(1,n-i+2):
            cum[j]=(cum[j-1]+dp[i-1][j])%mod
        if s[i-2]=="<":
            for j in range(n-i+1):
                dp[i][j]=(cum[n-i+1]-cum[j])%mod
        else:
            for j in range(n-i+1):
                dp[i][j]=(cum[j])%mod
    print(dp[n][0])
if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
s = '<'+input()[:-1]
dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][N] = 1
MOD = 10**9+7

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

print(dp[N][0])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# 参考 http://fluffyowl.hatenablog.com/entry/2019/01/08/114131

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

MOD = 10**9 + 7

# dp[i][j] : 左からi番目の数値まで確定していて、最後に置いた値が未使用の値のうちj番目に小さい値 である場合の数(0-indexed)
dp = [[0]*N for _ in range(N)]
for i in range(N):
    dp[0][i] = 1 # 一番左は0からN-1まで1通りずつ

for i in range(1,N):
    if s[i-1] == ">": # dp[i-1][j]をdp[i][j-1],...,dp[i][0] に足す
        x = dp[i-1][N-i]
        for j in reversed(range(N-i)): # jが大きい要素から順に累積和を足す
            dp[i][j] += x
            dp[i][j] %= MOD
            x += dp[i-1][j]
            x %= MOD
    else: # dp[i-1][j]をdp[i][j],...,dp[i][N-i-1] に足す。dp[i][j]が含まれる点に注意
        x = dp[i-1][0]
        for j in range(N-i): # jが小さい要素から順に累積和を足す
            dp[i][j] += x
            dp[i][j] %= MOD
            x += dp[i-1][j+1]
            x %= MOD

print(dp[N-1][0]) # 最後に置く値は必ず0番目に小さいのでdp[N-1][0]以外のdp[N-1]の要素は0

Submission status: Accepted

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

MOD = 10**9 + 7

# dp[i][j] : 左からi番目の数値まで確定していて、最後に置いた値が未使用の値のうちj番目に小さい値 である場合の数(0-indexed)
dp = [[0]*N for _ in range(N)]
for i in range(N):
    dp[0][i] = 1 # 一番左は0からN-1まで1通りずつ

for i in range(1,N):
    if s[i-1] == ">": # dp[i-1][j]をdp[i][j-1],...,dp[i][0] に足す
        x = dp[i-1][N-i]
        for j in reversed(range(N-i)): # jが大きい要素から順に累積和を足す
            dp[i][j] += x
            dp[i][j] %= MOD
            x += dp[i-1][j]
            x %= MOD
    else: # dp[i-1][j]をdp[i][j],...,dp[i][N-i-1] に足す。dp[i][j]が含まれる点に注意
        x = dp[i-1][0]
        for j in range(N-i): # jが小さい要素から順に累積和を足す
            dp[i][j] += x
            dp[i][j] %= MOD
            x += dp[i-1][j+1]
            x %= MOD

print(dp[N-1][0]) # 最後に置く値は必ず0番目に小さいのでdp[N-1][0]以外のdp[N-1]の要素は0

Submission status: Accepted

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: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
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[i][j]はi番目まで見て，Piよりも大きいものがj個ある時の通り数
    dp[0][-1]=1#0からスタートしたとみなす    
    
    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()

Submission status: Accepted

Solution code:
import sys
#sys = stdin.buffer.readline

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

#dp[i][j]
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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)]
# dp[i][j] = i番目まででi番目の数字より大きい数字が残りj個の通り数
# i番目の数字より小さい数はn = i + j + kよりk = n-i-j
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])
# print(*dp,sep = "\n")
# print(acum)

Submission status: Accepted

Solution code:
mod = 10**9+7

n = int(input())
s = input()
# 配るDPの初期値を入れておく
dp = [1]*n
for i in range(n-1):
    nxt = [0]*(n+1)
    # 前の相対順位は
    # [0, n-1-i]
    # 次の相対順位は
    # [0, n-2-i]
    # 今の順位がjのとき、
    # < → [i, n-2-i]に加算
    # > → [0, j-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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#            dp[i+1][j] = sum(dp[i][j+1:])
            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
#            dp[i+1][j] = sum(dp[i][:j+1])
    ss = bs%M
print(dp[-1][0]%M)

Submission status: Accepted

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


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

    # DP[i][j]はi文字目までをみたす順列のうち、最後がjで終わるものの個数
    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))  # type: int
    s = next(tokens)  # type: str
    solve(N, s)


if __name__ == '__main__':
    main()

Submission status: Accepted

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][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))  # type: int
    s = next(tokens)  # type: str
    solve(N, s)


if __name__ == '__main__':
    main()

Submission status: Accepted

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):
        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: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
s = input()
dp = [[0] * (n + 1) for _ in range(n + 1)]
# dp[i][j] - the number of ways to put numbers in prefix of size 'i' such that the last number is 'j'
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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]
        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
    #p2D(dp)
    print(sum(dp[n])%md)

main()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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 == '<':
        # 0,1,...,nがdp[n]に遷移する
        dp = prev[:-1].cumsum()
    else:
        # n+1,n+2,...がdp[n]に遷移する
        dp = prev[1:][::-1].cumsum()[::-1]
    dp %= MOD

answer = dp[0]
print(answer)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_3
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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)


print(dp[0])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

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):  # N-(i+1)+1 = N-i
            dp[j] = csum[j] if s[i_] == ">" else \
                (csum_ - csum[j] + MOD) % MOD
    return(dp[0])

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

Submission status: Accepted

Solution code:
# coding: utf-8

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):  # N-(i+1)+1 = N-i
            dp[j] = csum[j] if s[i_] == ">" else (csum_ - csum[j] + MOD) % MOD
    return(dp[0])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
dp = [[0]*(n+1) for _ in range(n+1)]
dp[1][1] = 1
for i in range(2, n+1):
    v = 0
    if s[i-2]=="<":
        for j in range(1,i+1):
            # j: 最後の数
            dp[i][j] = v
            v += dp[i-1][j]
            v %= M
        dp[i][i] = v
    else:
        for j in range(i,1,-1):
            # j: 最後の数
            dp[i][j] = v
            v += dp[i-1][j-1]
            v %= M
        dp[i][1] = v
#     print(dp)
ans = 0
for item in dp[n]:
    ans += item
    ans %= M
print(ans)