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

from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

def update(dp, AA):
    ndp = dp.copy()
    if ndp[-1] < AA:
        ndp.append(AA)
    else:
        bis = bisect.bisect_left(ndp, AA)
        ndp[bis] = AA
    return ndp

def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]

    A = [0]+list(map(int, input().split()))

    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1

    d = deque()
    d.append((1, [0, A[1]]))

    while d:
        v, dp = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            newdp = update(dp, A[i])
            dist[i] = len(newdp)-1
            d.append((i, newdp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

for i in range(n):
    copy = a[:]
    copy.pop(i)
    print(max(copy))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

a_max = max(a)
idx = [i for i, x in enumerate(a) if x==a_max]

if len(idx) > 1:
    for i in range(n):
        print(a_max)
else:
    for i in range(n):
        if a[i] == a_max:
            print(max(a[0:i]+a[i+1:]))
        else:
            print(a_max)
### BUGGY CODE ###

S = str(input())

for i in range(len(S)-1):
    if S[i] == '?':
        if S[i+1] == 'D':
            S = S[:i] + 'P' + S[i+1:]
        elif S[i+1] == '?':
            S = S[:i] + 'P' + S[i+1:]
        else:
            S = S[:i] + 'D' + S[i+1:]

if S[len(S)-1] == '?':
    S = S[:len(S)-1] + 'D'

print(S)

### FIXED CODE ###

S = list(str(input()))

for i in range(len(S)-1):
    if i == 0 and S[0] == '?':
        if S[i+1] == 'P':
            S[0] = 'D'
        else:
            S[0] = 'P'
    if S[i] == '?':
        if S[i+1] == 'P':
            S[i] = 'D'
        else:
            if S[i-1] == 'P':
                S[i] = 'D'
            else:
                S[i] = 'P'

if S[len(S)-1] == '?':
    S[len(S)-1] = 'D'

strS = "".join(S)

print(strS)
### BUGGY CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

import copy

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

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = defaultdict(int)
		self.data = [self.initVal] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		A, B = copy.deepcopy(a), copy.deepcopy(b)

		if len(A) >= len(B):
			for i in B:
				A[i] = 1
			return A
		else:
			for i in A:
				B[i] = 1
			return B

	# セグメント木の中身をリストAで初期化
	def initialize(self, A):
		for i in range(self.N):
			d = defaultdict(int)
			d[A[i]] = 1
			self.data[self.N0 - 1 + i] = d
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return len(m)


#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	Seg = SegmentTree(N)
	Seg.initialize(c)
	# print(Seg.data)
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		ans = Seg.query(l, r)
		print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		return a + b

	#k番目の値をxに更新
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])

	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	LR = []
	lastappeared = [None] * N

	ans = [0] * Q
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		LR.append([r, l, i])

	LR.sort(key = lambda x:x[0])
	Seg = SegmentTree(N)
	right = 0
	for r, l, i in LR:
		while right <= r:
			itr = c[right] - 1
			if lastappeared[itr] == None:
				Seg.update(right, 1)
			else:
				Seg.update(lastappeared[itr], 0)
				Seg.update(right, 1)
			lastappeared[itr] = right
			right += 1

		if l == 0:
			anspre = Seg.query(0, r)
		else:
			anspre = Seg.query(l, r)
		ans[i] = anspre

	for i in range(Q):
		print(ans[i])



if __name__ == '__main__':
	main()
### BUGGY CODE ###

N, X, Y = map(int, input().split())

g = [[]  for i in range(N)]
for i in range(N):
    u = i
    v = i + 1
    if v < N:
        g[u].append(v)
        g[v].append(u)

g[X - 1].append(Y - 1)
g[Y - 1].append(X - 1)

from collections import deque
dis = [[float('Inf')] * N for _ in range(N)]
count = [0] * (N - 1)
def bfs(i):
    d = [False] * N
    que = deque()
    #for j in g[i]:
    que.append(i)
    d[i] = True
    dis[i][i] = 0
    pre = i
    while que:
        p = que.popleft()

        for k in g[p]:
            if d[k]:
                continue
            else:
                d[k] = True
                que.append(k)
                dis[i][k] = dis[i][p] + 1
                dis[k][i] = dis[i][p] + 1
                count[dis[i][k] - 1] += 1 
                #count[dis[k][i] - 1] += 1
        pre = p

for i in range(N):
    bfs(i)

for i in range(N - 1):
    print(count[i] // 2)


### FIXED CODE ###

N, X, Y = map(int, input().split())

g = [[]  for i in range(N)]
for i in range(N):
    u = i
    v = i + 1
    if v < N:
        g[u].append(v)
        g[v].append(u)

g[X - 1].append(Y - 1)
g[Y - 1].append(X - 1)

from collections import deque
dis = [[float('Inf')] * N for _ in range(N)]
count = [0] * (N - 1)
def bfs(i):
    d = [False] * N
    que = deque()
    #for j in g[i]:
    que.append(i)
    d[i] = True
    dis[i][i] = 0
    pre = i
    while que:
        p = que.popleft()

        for k in g[p]:
            if d[k]:
                continue
            else:
                d[k] = True
                que.append(k)
                dis[i][k] = dis[i][p] + 1
                dis[k][i] = dis[i][p] + 1
                count[dis[i][k] - 1] += 1 
                #count[dis[k][i] - 1] += 1
        pre = p

for i in range(N):
    bfs(i)

for i in range(N - 1):
    print(count[i] // 2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
amount = [0]*n

for i in range(n):
    amount[i] = a.count(i+1)

for j in range(n):
    ans = 0
    for k in range(max(a)):
        ans += amount[k]*(amount[k]-1)//2
    ans -= amount[a[j]-1] -1
    print(ans)

### FIXED CODE ###

import numpy as np
def main():
    from collections import Counter
    n = int(input())
    a = tuple(map(int, input().split()))
    ans = 0
    c = Counter(a)
    for i in range(n):
        ans += c[i+1]*(c[i+1]-1)//2
    for j in range(n):
        print(ans - c[a[j]] + 1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from functools import reduce
import operator
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if not ANS[idx]:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if not ANS[i] : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if not ANS[i] : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.995
INIT = None
ANS = [INIT]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
mod = 10**9+7
dp=[0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[-1])

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])
### BUGGY CODE ###

# 2020/07/25
# M-SOLUTIONS プロコンオープン 2020 - C

# Input
n, k = map(int,input().split())
a = list(map(int,input().split()))

# Calc
pt = a[0]

for i in range(1, k):
    pt = pt * a[i]

for i in range(k, n):
    bef_pt = pt
    pt = pt * a[i] // a[i-k] 

    # Output
    if bef_pt < pt:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

# 2020/07/25
# M-SOLUTIONS プロコンオープン 2020 - C

# Input
n, k = map(int,input().split())
a = list(map(int,input().split()))

# Calc
for i in range(k, n):
    # Output
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import Counter
from functools import reduce
from operator import or_


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


N = int(input())
T = [Counter(prime_factorize(int(input()))) for _ in range(N)]

factors = reduce(or_, (c.keys() for c in T))
ans = 1
for factor in factors:
    ans *= factor ** max(c[factor] for c in T)
print(ans)


### FIXED CODE ###

from fractions import gcd
from functools import reduce


def lcm(a, b):
    return (a * b) // gcd(a, b)


N = int(input())
T = list(int(input()) for _ in range(N))

print(reduce(lcm, T))
### BUGGY CODE ###

def main():
    N, M  = [int(i) for i in input().split()]
    S  = [i == '1' for i in input()]
    cur = [(0, [])]
    while cur:
        nxt = []
        for loc, hist in cur:
            if loc == N:
                return ' '.join(str(j) for j in hist)
            for i in range(1, M + 1):
                nloc = loc + i
                if nloc > N or S[nloc]:
                    continue
                S[nloc] = True
                nxt.append((nloc, hist + [i]))
        cur = nxt
    return '-1'


print(main())


### FIXED CODE ###

def main():
    N, M  = [int(i) for i in input().split()]
    S  = [int(i) for i in input()]
    loc = N
    a = []
    while loc:
        for i in range(min(loc, M), 0, -1):
            if S[loc - i] == 1:
                continue
            a.append(i)
            loc -= i
            break
        else:
            return '-1'
    return ' '.join(str(i) for i in reversed(a))


print(main())
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

N =  int(readline())
HP = [tuple(map(int, readline().split())) for _ in range(N)]
HP.sort(key = sum)
INF = 10**18+3

dp = [INF]*(N+1)
dp[0] = 0

for i in range(N):
    hi, pi = HP[i]
    dp2 = dp[:]
    for j in range(N):
        if dp[j] > hi:
            break
        dp2[j+1] = min(dp2[j+1], dp[j]+pi)

    dp = dp2[:]

for ans in range(N+1):
    if dp[ans] == INF:
        ans -= 1
        break
print(ans)



### FIXED CODE ###

import sys
readline = sys.stdin.readline

N =  int(readline())
HP = [tuple(map(int, readline().split())) for _ in range(N)]
HP.sort(key = lambda x: x[0] + x[1])
INF = 1<<64

dp = [0]
for i in range(N):
    hi, pi = HP[i]
    dp += [INF]
    for j in range(i+1, 0, -1):
        if dp[j-1] > hi:
            continue
        dp[j] = min(dp[j], dp[j-1]+pi)
for ans in range(N+1):
    if dp[ans] == INF:
        ans -= 1
        break
print(ans)
### BUGGY CODE ###

t1,t2=map(int,input().split())
a1,a2=map(int,input().split())
b1,b2=map(int,input().split())
if t1*a1+t2*a2==t1*b1+t2*b2:
  print('infinity')
else:
  ans=0
  d=0 # a-b
  pre=0
  while True:
    if d!=0:
      if (d+(t1*a1-t1*b1))*d<=0:
        ans+=1
    d+=t1*a1-t1*b1
    if d!=0:
      if (d+(t2*a2-t2*b2))*d<=0:
        ans+=1
    d+=t2*a2-t2*b2
    if pre==ans:break
    pre=ans
  print(ans)


### FIXED CODE ###

t1,t2=map(int,input().split())
a1,a2=map(int,input().split())
b1,b2=map(int,input().split())
c1,c2=a1-b1,a2-b2
if t1*c1+t2*c2==0:
  print('infinity')
else:
  # t1+t2でどれだけ二人が離れるか。
  d=t1*c1+t2*c2
  if c2*d<0:
    print(0)
  elif abs(t2*c2)<abs(d):
    print(0)
  else:
    tmp=((t2*c2)//d)
    if (t2*c2)%d==0:
      print(2*tmp-2)
    else:
      print(2*tmp-1)
### BUGGY CODE ###

N=int(input())
S=[input()for _ in'_'*N]
x=[[0]*(2*N+1)for _ in'_'*N]
y=[[0]*N for _ in'_'*(2*N+1)]
T=333331
M=1333333333333333
for i in range(N):
	for j in range(2*N):
		x[i][j+1]=(x[i][j]*T+ord(S[i][j-N]))%M
		y[j+1][i]=(y[j][i]*T+ord(S[j-N][i]))%M
t=pow(T,N,M)
z=0
for a in range(N):
	for b in range(N):
		for i in range(N):
			if(x[-N+a+i][b+N]-x[-N+a+i][b]*t)%M!=(y[a+N][-N+b+i]-y[a][-N+b+i]*t)%M:
				break
		else:
			z+=1
print(z)


### FIXED CODE ###

N=int(input())
S=[input()for _ in'_'*N]
z=0
for k in range(-N,0):
	for t in range(N*N):
		i=t//N
		j=t%N
		if S[i][j+k]!=S[j][i+k]:
			break
	else:
		z+=N
print(z)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
ikeruheya = [[] for i in range(n)]
ans = [0]*(n+1)
check = [0]*n

for i in range(m):
    ikeruheya[a[i][0]-1].append(a[i][1])
    ikeruheya[a[i][1]-1].append(a[i][0])
    
next=[1]
count = 1
while len(next) != 0 and count < n + 1:
    imaheya = next.pop(0)
    for j in range(len(ikeruheya[imaheya-1])):
        if check[ikeruheya[imaheya-1][j]-1]==0:
            ans[ikeruheya[imaheya-1][j]]= imaheya 
            check[ikeruheya[imaheya-1][j]-1] = 1
            next.append(ikeruheya[imaheya-1][j])
            
print("Yes")
for i in range(2, n+1):
    print(ans[i])

    
    
    


### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
a=[list(map(int, input().split())) for i in range(m)]
b=[[] for j in range(n)] 

michi=[-1]*(n)
michi[0]=0
heya=[]


for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])



heya.append(1)


while len(heya):
    now=heya.pop(0)-1
    
    for i in range(len(b[now])):
        if michi[b[now][i]-1] == -1:
            heya.append(b[now][i])
            michi[b[now][i]-1] = now+1
print("Yes")
for i in range(1,n):
    print(michi[i])
### BUGGY CODE ###

class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


class PowPreCalc:
    def __init__(self, *, b, m, mod):
        """(b**m)%mod"""
        res = [1]
        t = 1
        for _ in range(m):
            t = t * b % mod
            res.append(t)
        self._res = res

    def get_pow(self, m):
        """(b**m)%mod"""
        return self._res[m]


def main():
    MOD = 10 ** 9 + 7

    K = int(input())
    S = input()

    N = len(S)

    calc = Calc(max_value=N - 1 + K, mod=MOD)

    p26 = PowPreCalc(b=26, m=K, mod=MOD)
    p25 = PowPreCalc(b=25, m=K, mod=MOD)

    ans = 0
    for tail_len in range(K + 1):
        ans = (ans
               + calc.nCr(N - 1 + K - tail_len, N - 1) * p26.get_pow(tail_len) * p25.get_pow(K - tail_len)
               ) % MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


class PowPreCalc:
    def __init__(self, *, b, m, mod):
        """(b**m)%mod"""
        res = [1]
        t = 1
        for _ in range(m):
            t = t * b % mod
            res.append(t)
        self._res = res

    def get_pow(self, m):
        """(b**m)%mod"""
        return self._res[m]


def main():
    MOD = 10 ** 9 + 7

    K = int(input())
    S = input()

    N = len(S)

    calc = Calc(max_value=N - 1 + K, mod=MOD)

    p26 = PowPreCalc(b=26, m=K, mod=MOD)
    p25 = PowPreCalc(b=25, m=K, mod=MOD)

    ans = 0
    for tail_len in range(K + 1):
        ans = (ans
               + calc.nCr(N - 1 + K - tail_len, N - 1) * p26.get_pow(tail_len) * p25.get_pow(K - tail_len)
               ) % MOD

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math

def comb(n, r, mod):
    return math.factorial(n + r - 1)//(math.factorial(n - 1)*math.factorial(r))%mod

def nCrModp(n, r, p): 
    if (r > n- r): 
        r = n - r   
  
    C = [0 for i in range(r + 1)] 
  
    C[0] = 1
  
    # One by constructs remaining rows of Pascal 
    # Triangle from top to bottom 
    for i in range(1, n + 1): 
  
        # Fill entries of current row  
        # using previous row values 
        for j in range(min(i, r), 0, -1): 
  
            # nCj = (n - 1)Cj + (n - 1)C(j - 1) 
            C[j] = (C[j] + C[j-1]) % p 
  
    return C[r]

s = int(input())
mod = 10**9 + 7
ans = 1

if s < 3:
    ans = 0

for i in range(2, 700): #分割数, 1の時は1通りなので除外
    if s < 3*i:
        break
    r = s - i*3
    ans = (ans + nCrModp(s - 2*i - 1, s - 3*i, mod))%mod

print(ans)


### FIXED CODE ###

import math

def comb(n, r, mod):
    return math.factorial(n + r - 1)//(math.factorial(n - 1)*math.factorial(r))%mod

s = int(input())
mod = 10**9 + 7
ans = 1

if s < 3:
    ans = 0

for i in range(2, 700): #分割数, 1の時は1通りなので除外
    if s < 3*i:
        break
    r = s - i*3
    ans = (ans + comb(i, r, mod))%mod

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

a = input().split()
b = input().split()

ans = 0

for i in range(int(a[0])-int(a[1])+1):
    sum = 0
    for j in range(int(a[1])):
        sum += (1 + int(b[i+j]))/2
    if ans < sum:
        ans = sum

print(ans)

### FIXED CODE ###

a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

sum = 0
ans = 0

for i in range(a[0]):
    sum += (1 + b[i])/2
    if i > a[1]-1:
        sum -= (1 + b[i-a[1]])/2
    if ans < sum:
        ans = sum

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

n=int(input())
a={"3","5","7"}
ans=0
for v in range(n+1):
    k=set(list(str(v)))
    if k ==a:
        ans+=1
print(ans)

### FIXED CODE ###

N = int(input())
def dfs(s): 
    if int(s) > N:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in '753') else 0
    # s 自体が七五三数なら +1 
    for c in '753':
        ret += dfs(s + c)
    return ret
print(dfs('0'))
### BUGGY CODE ###

"""二分探索"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())
L = list(map(int, input().split()))

L.sort()
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        l = j; r = n
        while l+1 < r:
            c = (l+r)//2
            if L[c] < L[i]+L[j]:
                l = c
            else:
                r = c
        ans += l-j
        
print(ans)

### FIXED CODE ###

"""二分探索"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())
L = list(map(int, input().split()))

L.sort()
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        l = j; r = n
        while l+1 < r:
            c = (l+r)//2
            if L[c] < L[i]+L[j]:
                l = c
            else:
                r = c
        ans += l-j
        
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    t = input()
    dp = [[[0, ""] for _ in range(len(t)+1)] for _ in range(len(s)+1)]
    for i, cs in enumerate(s, start=1):
        for j, ct in enumerate(t, start=1):
            if cs == ct:
                dp[i][j][0] = dp[i-1][j-1][0] + 1
                dp[i][j][1] = dp[i-1][j-1][1] + cs
            else:
                dp[i][j][0] = max(dp[i-1][j][0], dp[i][j-1][0])
                dp[i][j][1] = dp[i-1][j][1] if dp[i][j][0] == dp[i -
                                                                 1][j][0] else dp[i][j-1][1]
    print(dp[-1][-1][-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

# python3だとTLE,pypy3だとAC
def main():
    s = input()
    t = input()
    dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
    for i, cs in enumerate(s, start=1):
        for j, ct in enumerate(t, start=1):
            if cs == ct:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    ans = ""
    i = len(s)
    j = len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i] + ans

    print(ans)


if __name__ == "__main__":
    main()