Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def f(k, a_s):
    md = 10 ** 9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    dp[0][0] = 1
    dpi = dp[0]
    for i, a in enumerate(a_s[:-1]):
        dpi1 = dp[i + 1]
        dpi1[0] = s = dp[i][0] % md
        for j in range(1, a + 1):
            dpi1[j] = s = (s + dpi[j]) % md
        for j in range(a + 1, k + 1):
            dpi1[j] = s = (s + dpi[j] - dpi[j - a - 1]) % md
        dpi=dpi1
    return sum(dp[-1][k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(k, a_s))


### FIXED CODE ###

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))
### BUGGY CODE ###

from collections import deque
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]


class Node:
    def __init__(self, val):
        self.val = val
        self.child_list = []
        self.cnt = 0

class my_tree:
    def __init__(self, tree_list):
        self.node_list = []

        for i in range(N):
            self.node_list.append(Node(i+1))

        for a, b in tree_list:
            a, b = int(a), int(b)

            child_node = self.node_list[b-1]
            parent_node = self.node_list[a-1]
            self.node_list[a-1].child_list.append(child_node)
            self.node_list[b-1].child_list.append(parent_node)
        
    def adding(self, query_list):
        for a, data in query_list:
            a, data = int(a), int(data)
            self.node_list[a-1].cnt += data

        stack = deque([self.node_list[0]])
        parent_node_list = [self.node_list[0]]*(N + 1)

        while True:
            v = stack.pop()
            for child in v.child_list:
                if child != parent_node_list[v.val -1]:
                    child.cnt += v.cnt
                    parent_node_list[child.val -1] = v
                    stack.append(child)
            
            if not stack:
                break


ins = my_tree(tree_list)
ins.adding(query_list)
print(*[node.cnt for node in ins.node_list])


### FIXED CODE ###

N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]

query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

val_list = [0 for _ in range(N)]

linked_node_list = [[] for _ in range(N)]

for a, b in tree_list:
    a, b = int(a)-1, int(b) -1
    linked_node_list[a].append(b)
    linked_node_list[b].append(a)


for index, val in query_list_int:
    val_list[index-1] += val

stack = [0]
parent = [0] * (N+1)

while True:
    v=stack.pop()
    for child in linked_node_list[v]:
        if child != parent[v]:
            parent[child] = v
            stack.append(child)
            val_list[child] += val_list[v]
    if not stack:
        break

print(*val_list)
### BUGGY CODE ###

N=int(input())
A=map(int,input().split())
border=10**18

ans=1
for a in A:
    ans*=a

if ans>border:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
border=10**18

ans=1
for a in A:
    ans*=a
    if ans>border:
        print(-1)
        exit()
    elif ans==0:
        print(0)
        exit()

print(ans)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
Slist = []
for i in range(N):
    S = input()
    Slist.append(S)
Slist.sort(key=len)
dic = defaultdict(lambda:defaultdict(int))
ans = 0
for S in Slist:
    alp = set()
    letter = S
    for i in range(len(S)):
        alp.add(letter[0])
        letter = letter[1:]
        alpdic = dic[letter]
        for X in alpdic.keys():
            if X in alp:
                ans += alpdic[X]
    dic[S[1:]][S[0]] += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

N = int(input())
Slist = []
for i in range(N):
    S = input()
    Slist.append(S)
Slist.sort(key=len)
dic = defaultdict(lambda:defaultdict(int))
ans = 0
for S in Slist:
    alp = set()
    l = len(S)
    RH = RollingHash(S,37,10**18+9)
    for i in range(len(S)):
        alp.add(S[i])
        alpdic = dic[RH.get(i+1,l)]
        for X in alpdic.keys():
            if X in alp:
                ans += alpdic[X]
    dic[RH.get(1,l)][S[0]] += 1
print(ans)
### BUGGY CODE ###

H,N = map(int,input().split())
A = [0]*N
B = [0]*N
inf = float('inf')
for i in range(N):
    A[i], B[i] = map(int,input().split())
dp = [inf]*(H+1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        if j >= A[i]:
            dp[j] = min(dp[j],dp[j-A[i]] + B[i])
        else: # ワンパンで倒せる場合
            dp[j] = min(dp[j],B[i])
print(dp[H])
# print(dp)





### FIXED CODE ###

H,N = map(int,input().split())
A = [0]*N
B = [0]*N
inf = float('inf')
for i in range(N):
    A[i], B[i] = map(int,input().split())
dp = [inf]*(H+1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        if j >= A[i]:
            dp[j] = min(dp[j],dp[j-A[i]] + B[i])
        else: # ワンパンで倒せる場合
            dp[j] = min(dp[j],B[i])
print(dp[H])
# print(dp)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]
S_set = sorted(list(set(S)))
#print(S_set)
cnt = [0 for i in range(len(S_set))]
word_buf = []
mmax = -1

for i in range(len(S_set)) :
    cnt[i] = S.count(S_set[i])
    if i == 0 :
        word_buf.append(S_set[i])
    else :
        if cnt[i] < mmax :
            pass
        elif cnt[i] == mmax :
            word_buf.append(S_set[i])
        elif cnt[i] > mmax :
            word_buf.clear()
            word_buf.append(S_set[i])
    mmax = max(mmax,cnt[i]) # 現時点での最大値

word_buf = sorted(word_buf)
for i in range(len(word_buf)) :
    print(word_buf[i])

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [''] * N
for i in range(N) :
    S[i] = input()
S = Counter(S).most_common()
c = S[0][1]

print(*sorted([a for a,s in S if s==c]),sep="\n")
### BUGGY CODE ###

h, w = [int(i) for i in input().split()]
a = []
b = [""] * w
for _ in range(h):
    s = input()
    a.append(s)
    for i, j in enumerate(s):
        b[i] += j


def c(s):
    m = 0
    n = 0
    for i in s:
        if i == ".":
            n += 1
            m = max(n, m)
        else:
            n = 0
    return m


print(c(max(a, key=c)) + c(max(b, key=c)) - 1)


### FIXED CODE ###

h, w = [int(i) for i in input().split()]
s = [input() for _ in range(h)]

a = [[0]*w for _ in range(h)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for i in range(h):
    k = 0
    for j in reversed(range(w)):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for j in range(w):
    k = 0
    for i in range(h):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for j in range(w):
    k = 0
    for i in reversed(range(h)):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
b = max([max(i) for i in a])
print(0 if b == 0 else b-3)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

maxVal = N + max(A)
ans = 0

L = defaultdict(int)
R = defaultdict(int)
for x in range(1, maxVal+1):
    for i in range(1, N+1):
        if i + A[i-1] == x:
            L[i+A[i-1]] += 1

    for j in range(1, N+1):
        if j - A[j-1] == x:
            R[j-A[j-1]] += 1


for x in range(1, maxVal+1):
    ans += L[x] * R[x]

print(ans)


### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

maxVal = N + max(A)
ans = 0

candidatesL = defaultdict(int)
for i in range(1, N+1):
    candidatesL[i+A[i-1]] += 1

candidatesR = defaultdict(int)
for j in range(1, N+1):
    candidatesR[j-A[j-1]] += 1

ans = 0
for x in candidatesL.keys():
    ans += candidatesL[x] * candidatesR[x]

print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())

L=[0]*M
R=[0]*M
common = set(range(1, N+1))
for i in range(M):
  L, R = map(int, input().split())
  common = common & set(range(L,R+1))
print(len(common))

### FIXED CODE ###

N,M = map(int, input().split())

L=[0]*M
R=[0]*M
for i in range(M):
  L[i], R[i] = map(int, input().split())
    
print(max(min(R)-max(L)+1,0))
### BUGGY CODE ###

n = int(input())
def sqe(a, b, c):
    D = (b**2 - 4*a*c) ** (1/2)
    x_1 = (-b + D) / (2 * a)

    return x_1
  
for i in range(1,n+1):
  cnt = 0
  for x in range(1,80):
    if n-x**2<=0:
      break
    for y in range(1,int((n-x*2)**0.5)+1):
      if x**2+y**2+x*y>i:
        break
      x_1 = sqe(1,x+y,x**2+y**2+x*y-i)
      if x_1.is_integer() and x_1>0:
        cnt += 1
  print(cnt)

### FIXED CODE ###

n = int(input())
def solve(n):
  l = [0]*(n**3)
  for x in range(1,n+1):
    for y in range(1,n+1):
      for z in range(1,n+1):
        l[x**2+y**2+z**2+x*y+y*z+z*x] += 1
  return l
l = solve(100)
print(*l[1:n+1])
### BUGGY CODE ###

from math import sqrt, floor
from bisect import bisect_left


def search(x):
    global p, lp
    i = bisect_left(p, x)
    return i != lp and p[i] == x


p = [2]
for i in range(3, 50000, 2):
    for j in range(3, floor(sqrt(i)) + 1, 2):
        if not i % j:
            break
    else:
        p.append(i)
lp = len(p)

while True:
    n = int(input())
    if not n:
        break
    if n & 1:
        print(int(search(n - 2)))
        continue
    n2 = n // 2
    cnt = 0
    for i in p:
        if n2 < i:
            break
        if search(n - i):
            cnt += 1
    print(cnt)

### FIXED CODE ###

from math import sqrt, floor

p = [2]
for i in range(3, 50000, 2):
    for j in range(3, floor(sqrt(i)) + 1, 2):
        if not i % j:
            break
    else:
        p.append(i)
sp = set(p)

while True:
    n = int(input())
    if not n:
        break
    if n & 1:
        print(int(n - 2 in sp))
        continue
    n2 = n // 2
    cnt = 0
    for i in p:
        if n2 < i:
            break
        if n - i in sp:
            cnt += 1
    print(cnt)
### BUGGY CODE ###

from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math
# import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) 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 MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))

n, a = II(), LI()
maxi = max(GCD_LIST(a[1:]), GCD_LIST(a[:n-1]))
for i in range(1,n-1):
    left_gcd = GCD_LIST(a[:i])
    right_gcd = GCD_LIST(a[i+1:])
    maxi = max(maxi, fractions.gcd(left_gcd, right_gcd))

print(maxi)


### FIXED CODE ###

from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math
# import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) 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 MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


n, a = II(), LI()
left = [0] * (n+1)
right = [0] * (n+1)

for i in range(1, n+1):
    left[i] = fractions.gcd(left[i-1], a[i-1])

for i in range(n-1, -1, -1):
    right[i] = fractions.gcd(right[i+1], a[i]) 

# print(left)
# print(right)

maxi = -INF

for i in range(n):
    maxi = max(maxi, fractions.gcd(left[i],right[i+1]))

print(maxi)
### BUGGY CODE ###

import math

n = int(input())
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(n - 1)]

def fact(m):
  return m * fact(m-1) % 1000000007 if m != 1 else 1
 
fact_n_1 = math.factorial(n-1)

e = [None] * (n-1)
for i in range(n-1):
  if i == 0:
    e[i] = fact_n_1
  else:
    e[i] = (e[i - 1] + fact_n_1 // (i + 1)) % 1000000007

print(sum(e_i * d_i % 1000000007
          for i, (d_i, e_i) 
          in enumerate(zip(d, e))) % 1000000007 ) 

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n = int(input())
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(n - 1)]

def pow(x, y):
    if y == 0:
        return 1
    ans = 1
    while y > 1:
        if y % 2 != 0:
            ans *= x
            ans %= 1000000007
        x *= x
        x %= 1000000007
        y //= 2
    return ans * x % 1000000007

def fact(m):
  return m * fact(m-1) % 1000000007 if m != 1 else 1
 
fact_n_1 = fact(n-1)

e = [None] * (n-1)
for i in range(n-1):
  if i == 0:
    e[i] = fact_n_1
  else:
    e[i] = (e[i - 1] + fact_n_1 * pow(i + 1, 1000000005)) % 1000000007

print(sum(e_i * d_i % 1000000007
          for i, (d_i, e_i) 
          in enumerate(zip(d, e))) % 1000000007 )
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
h = [0] + h
dp = [float("inf")]*(n+1)
dp[0] = 0
dp[1] = 0
for i in range(1,n+1):
    for j in range(i+1,min(i+k+1,n+1)):
        dp[j] = min(abs(h[i] - h[j]) + dp[i], dp[j])
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")]*n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i-j >= 0:
            dp[i] = min(abs(h[i-j] - h[i]) + dp[i-j], dp[i])
print(dp[-1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
b=0

for i in range(0,N-1):
    for j in range(i+1,N):
        b+=A[i]*A[j]
        
print(b%(10**9+7))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
b=0
c=0

for j in range(0,len(A)):
    c+=A[j]

for i in range(0,len(A)):
        c=c-A[i]
        b+=A[i]*c
        
print(b%(10**9+7))
### BUGGY CODE ###

n = int(input())

p = 1
for i in range(1, n+1):
  p *= i
print(p % (10**9 + 7))

### FIXED CODE ###

n = int(input())

pw = 1
num = 1
for i in range(n):
  pw = pw*num % (10**9+7)
  num += 1
  
print(pw)
### BUGGY CODE ###

a, b, k = map(int, input().split())
for _ in range(k):
    if a != 0:
        a -= 1
    else:
        b -= 1
print(a,b)

### FIXED CODE ###

a, b, k = map(int, input().split())
if k >= a + b:
    a = 0
    b = 0
elif a <= k:
    b = b + a - k
    a = 0
else:
    a -= k
print(a,b)
### BUGGY CODE ###

def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

def input_list():
  return list(map(int, input().split()))

def input_list_str():
  return list(map(str, input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  r, g, b, n = input_list()
  ans = 0
  for x in range(n//r+1):
    for y in range(n//g+1):
      rr = r*x
      gg = g*y
      if rr + gg > n:
        continue
      bb = (n - rr - gg)
      if bb % b != 0:
        continue
      ans += 1
  print(ans)
  
import math
import fractions
import collections
import itertools
from functools import reduce
main()

### FIXED CODE ###

def input_list():
  return list(map(int, input().split()))

def main():
  r, g, b, n = input_list()
  ans = 0
  for x in range(n//r+1):
    for y in range(n//g+1):
      rr = r*x
      gg = g*y
      if rr + gg > n:
        continue
      bb = (n - rr - gg)
      if bb % b != 0:
        continue
      ans += 1
  print(ans)

main()
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M=LI()
RES = [-1]*(N+1)
RES[N] = 0.0

MP=[[] for i in range(N+1)]
for _ in range(M):
    i, j = LI()
    MP[i].append(j)
# print(MP)

for i in range(N-1, 0, -1):
    div = len(MP[i])
    next_E = 0
    for j in MP[i]: next_E += RES[j] + 1
    RES[i] = next_E / div

len_1 = len(MP[1])

# print("len_1: {}".format(len_1))
# print(RES)

result = RES[1]
RESN = [0]*(N+1)
for i in range(1, N-1):
    skip = False
    max_j, max_value = 0, 0

    for j in MP[i]:
        if RES[j] > max_value:
            max_value = RES[j]
            max_j = j

    for k in range(N-1, 0, -1):
        div = 0
        next_E = 0
        for j in MP[k]:
            if k != i or j != max_j:
                div += 1
                next_E += RESN[j] + 1
        if div == 0:
            skip = True
            break
        else:
            RESN[k] = next_E / div
    if not skip:
        result = min(result, RESN[1])

print(result)


### FIXED CODE ###

def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)
 
    # 確率DP
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])
 
    # 期待値DP
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])
 
    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        # 各vに対して、辺vwのうちE[w]が最大のものを削除する
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)
 
    print(ans)
resolve()
### BUGGY CODE ###

n=int(input())
s=input()
min=300000
for i in range(n):
    number=s[:i:].count("W")+s[i+1:].count("E")
    if min>number:
        min=number
print(min)


### FIXED CODE ###

n=int(input())
s=input()
w=[0]*n
e=[0]*n
for i in range(n):
    if s[i]=="W":
        if i==0:
           w[i]+=1
        else:
            w[i]+=w[i-1]+1
            e[i]+=e[i-1]
    else:
        if i==0:
            e[i]+=1
        else:
            e[i]+=e[i-1]+1
            w[i]+=w[i-1]
min=9999999
for i in range(n):
    if i==0:
        num=e[n-1]-e[i]

    else:
        num=w[i-1]+e[n-1]-e[i]
    if min>num:
        min=num
print(min)
### BUGGY CODE ###

import collections
n = int(input())
ls = [input() for i in range(n)]    
c = collections.Counter(ls)
count = c.most_common()[0][1]
ans = []
if c.most_common()[0][1] == 1:
    ls.sort()
    for i in ls:
        print(i)
elif c.most_common()[-1][1] == 2 and c.most_common()[0][1] == 2:
    ls.sort()
    for i in ls:
        print(i)
else:
    for i in range(len(c)):
        if c.most_common()[i][1] == count:
            ans.append(c.most_common()[i][0])
        else:
            break   
    ans.sort()
    for i in ans:
      print(i)

### FIXED CODE ###

import collections
from collections import Counter

n = int(input())
ls = [input() for i in range(n)]    
c = Counter(ls).most_common()

count = c[0][1]
ans = []

for i in range(len(c)):
    if c[i][1] == count:
        ans.append(c[i][0])
    else:
        break   
ans = sorted(ans)
for i in ans:
    print(i)
### BUGGY CODE ###


def LCS(s,t):
    ret = ''
    ls,lt = len(s), len(t)
    
    # dp[i][j] : s_i, t_iでのLCS
    dp = [[0]*(lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            if s[i]==t[j]:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    
    if dp[ls][lt]==0:
        return ret
    i,j = ls, lt
    while i>0 and j>0:
        if s[i-1] == t[j-1]:
            ret += s[i-1]
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
    return ret[::-1]

n = int(input())
S = input()
ans = 0
for i in range(1, n//2 + 2):
    s = S[:i]
    t = S[i:]
    ans = max(ans, len(LCS(s,t)))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
dp = [[0]*5005 for _ in range(5005)]
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i]!=s[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
S = LI()
T = LI()

MOD = 10 ** 9 + 7


def main():
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
            dp[i][j] %= MOD
            if S[i - 1] == T[j - 1]:
                x = 1 + dp[i - 1][j - 1]
                dp[i][j] = (dp[i][j] + x) % MOD
    
    ans = (dp[-1][-1] + 1) % MOD
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
S = LI()
T = LI()

MOD = 10 ** 9 + 7


def main():
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
            dp[i][j] %= MOD
            if S[i - 1] == T[j - 1]:
                x = 1 + dp[i - 1][j - 1]
                dp[i][j] = (dp[i][j] + x) % MOD
    
    ans = (dp[-1][-1] + 1) % MOD
    print(ans)


if __name__ == "__main__":
    main()