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

from collections import defaultdict


def longest_common_subsequence(s, t):
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    return dp[-1][-1]


def longest_common_subsequence2(s, t):
    dp = [0 for _ in range(len(t) + 1)]
    for i in range(len(s)):
        tmp = dp[:]
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[j + 1] = tmp[j] + 1
            else:
                dp[j + 1] = max(dp[j + 1], dp[j])
    return dp[-1]


def main():
    n = int(input())
    for _ in range(n):
        X, Y = input(), input()
        print(longest_common_subsequence2(X, Y))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict


def longest_common_subsequence(s, t):
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    return dp[-1][-1]


def longest_common_subsequence2(s, t):
    dp = [0] * (len(t) + 1)
    for i in range(len(s)):
        si = s[i]
        tmp = dp[:]
        for j in range(len(t)):
            if si == t[j]:
                dp[j + 1] = tmp[j] + 1
            elif dp[j + 1] < dp[j]:
                dp[j + 1] = dp[j]
    return dp[-1]


def main():
    n = int(input())
    for _ in range(n):
        X, Y = input(), input()
        print(longest_common_subsequence2(X, Y))


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

N = int(input())
A = input().split()

A_set = set(A)

#ボールに書かれている 数字の内訳を辞書に登録
A_dic = {}
#すべてのボールから同じボールを取り出す方法数
all_count = 0

for a in A_set:
    count_a = A.count(a)
    all_count += (count_a * (count_a - 1) // 2)
    A_dic.update({a:A.count(a)})

#n個あるボールから 1個取り除いた場合の方法数
#すべてのボールから取り出す方法数 - (n-1)通り

for i in range(N):
    print(all_count - A_dic.get(A[i])+1)


### FIXED CODE ###

import collections

N = int(input())
A = input().split()

#A_set = set(A)

#ボールに書かれている 数字の内訳を辞書に登録
A_dic = collections.Counter(A)

#すべてのボールから同じボールを取り出す方法数
all_count = 0

for a in A_dic.keys():
    count_a = A_dic.get(a)
    all_count += (count_a * (count_a - 1) // 2)

#n個あるボールから 1個取り除いた場合の方法数
#すべてのボールから取り出す方法数 - (n-1)通り

for i in range(N):
    print(all_count - A_dic.get(A[i])+1)
### BUGGY CODE ###

import sys
S = sys.stdin.readline().strip()
Q = int(sys.stdin.readline().strip())

for i in range(Q):
    Query = sys.stdin.readline()
    if len(Query) == 2:
        S = S[::-1]
    else:
        a, b, c = Query.split()
        if b == '1':
            S = c + S
        else:
            S += c
print(S)

### FIXED CODE ###

from collections import deque
S = input()
que = deque()
que.append(S)
Q = int(input())
Front_flag = 1

for i in range(Q):
    Query = tuple(input().split())
    if len(Query) == 1:
        Front_flag = 1 - Front_flag
    else:
        a, b, c = Query
        if (Front_flag + int(b)) % 2 == 1:
            que.append(c)
        else:
            que.appendleft(c)

ans = ''.join(que)
if Front_flag:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

arr = []
tmp = 0

for n in P:
  arr.append((n*(n+1)/2)/n)

for i in range(0, N - K + 1):
  max_value = 0
  max_value = sum(arr[i:i+K])
  if max_value >= tmp: 
    tmp = max_value

print(tmp)

### FIXED CODE ###

import queue

N, K = map(int, input().split())
P = list(map(int, input().split()))

q = queue.Queue()

#arr = [(n+1)/2 for n in P]
mx = 0
s = 0

for i in range(N):
  s += P[i]+1
  q.put(P[i]+1)
  if q.qsize() > K:
    s -= q.get()
  if q.qsize() == K:
    mx = max(mx, s)

ans = mx/2
print(ans)
### BUGGY CODE ###

from collections import deque

h,w = [int(x) for x in input().split()]
m = [list(input()) for x in range(h)]

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

while q:
    v = q.popleft()
    count = 0
    for i in m:
        jj = set(i)
        if len(jj) == 2:
            break
    else:
        break
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1

######
ans = 0
for i in d:
    ans = max(ans,max(i))
print(ans)

### FIXED CODE ###

from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "#":
            q.append([i,j])
            d[i][j] = 0

aa = 0
while q:
    v = q.popleft()
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "#"
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1
            aa = max(aa,d[ny][nx])

######
print(aa)
### BUGGY CODE ###

n, k = map(int, input().split(' '))
s = input()
if k >= n:
  print(n)
  exit()
  
s10 = []
cnt = 0
s_prev = '1'
for si in s+'x':
  if si == s_prev:
    cnt += 1
  else:
    s10.append(cnt)
    cnt = 1
  s_prev = si
if s[-1] == '0':
  s10.append(0)
if len(s10) < 2*k + 1:
  print(n)
  exit()

sum_max= 0
for i in range(len(s10)//2+1):
  sum_i = sum(s10[2*i:2*i+2*k+1])
  sum_max = max(sum_i, sum_max)
  
print(sum_max)

### FIXED CODE ###

n, k = map(int, input().split(' '))
s = input()
if k >= n:
  print(n)
  exit()
  
s10 = []
cnt = 0
s_prev = '1'
for si in s+'x':
  if si == s_prev:
    cnt += 1
  else:
    s10.append(cnt)
    cnt = 1
  s_prev = si
if s[-1] == '0':
  s10.append(0)
if len(s10) < 2*k + 1:
  print(n)
  exit()

sum_i = sum(s10[:2*k+1])
sum_max= sum_i

for i in range(len(s10)//2-k):
  sum_i += (s10[2*i + 2*k + 1] + s10[2*i + 2*k + 2] - s10[2*i] - s10[2*i+1])
  sum_max = max(sum_i, sum_max)
  
print(sum_max)
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())
L = [(a, b, c) for a in range(1, k+1) for b in range(1, k+1) for c in range(1, k+1)]
ans = 0
for l in L: ans += gcd_list(l)
print(ans)

### FIXED CODE ###

import math

k = int(input())

ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        tmp = math.gcd(a, b)
        for c in range(1, k+1):
            ans += math.gcd(tmp, c)
print(ans)
### BUGGY CODE ###

import math

N,A,B,K=map(int,input().split())

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


ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    if (K-(A*i))%B==0:
        if (K-(A*i))//B<=N:
            ANS = (ANS+(Combi(N,i)*Combi(N,(K-(A*i))//B)))%998244353

print(ANS)

### FIXED CODE ###

N,A,B,K=map(int,input().split())
mod=998244353

INV=[None]*(N+1)
for i in range(1,N+1):
    INV[i]=pow(i,mod-2,mod)

Combi=[None]*(N+1)
Combi[0]=1
Combi[1]=N
for i in range(2,N//2+2):
    Combi[i]=Combi[i-1]*(N-i+1)*INV[i] %mod
for i in range(N//2+2,N+1):
    Combi[i]=Combi[N-i]


ANS=0

if B>A:
    (A,B)=(B,A)

ran=K//A

for i in range(min(ran,N)+1):
    q, r = divmod(K-(A*i), B)
    if r==0 and q<=N:
        ANS = (ANS+(Combi[i]*Combi[q])%mod)%mod

print(ANS)
### BUGGY CODE ###

from sys import stdin
import sys
sys.setrecursionlimit(10**6)
def S(): return stdin.readline().rstrip()

a = S()
def f(t,a):
    if t == a:
        return True
    elif len(a)<len(t):
        return False
    else:
        strl = {0:'dream',1:'dreamer',2:'erase',3:'eraser'}
        for i in range(4):
            tmp = strl[i]
            if t+tmp in a[:len(t+tmp)]:
                if f(t+tmp,a):
                    return True
        return False

if f('',a):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

from sys import stdin
def S(): return stdin.readline().rstrip()

a = S()
strl = ['dream','dreamer','erase','eraser']
t = ''
for i in range(len(a)-1,-1,-1):
    if 7<len(t):
        print('NO')
        exit()
    else:
        t = a[i]+t
        if t in strl:
            t = ''

print('YES')
### BUGGY CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

N, M = list(map(int, input().split()))
uv = []
for i in range(M):
	uv.append(list(map(int, input().split())))
S, T = list(map(int, input().split()))
G = [dict() for i in range(N+1)]
for i in range(N + 1):
	G[i]["eda"] = []
	G[i]["num"] = -1
for i in range(M):
	G[uv[i][0]]["eda"].append(uv[i][1])
node_set = [S]
G[S]["num"] = 0
time = 1
while True:
	judge = 0
	first = []
	second = []
	for node in node_set:
		first.extend(G[node]["eda"])
	for node in first:
		second.extend(G[node]["eda"])
	node_set = []
	for node in second:
		if len(G[node]["eda"]) > 0:
			for eda in G[node]["eda"]:
				if eda == T:
					print(time)
					exit()
				if G[eda]["num"] == -1:
					node_set.append(eda)
					G[eda]["num"] == time
					judge = 1
	if judge == 0:
		print(-1)
		exit()
	time += 1

### FIXED CODE ###



import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


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

graph = [[] for _ in range(3*N)]

for i in range(M):
	u, v = list(map(int, input().split()))
	u -= 1
	v -= 1
	graph[u%(3*N)].append((v + N)%(3*N))
	graph[(u + N) % (3 * N)].append((v+2*N)%(3*N))
	graph[(u + 2*N) % (3 * N)].append(v % (3 * N))
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print(dist[T]//3)
else:
	print(-1)
### BUGGY CODE ###

N = int(input())
L = [0] + list(map(int, input().split())) + [0]
edge = []
distance = 0
for i in range(N+1):
    distance += abs(L[i] - L[i+1])
for i in range(1,N+1):
    if (L[i] -L[i-1])*(L[i+1] - L[i] )>=0:
        pass
    else:
        edge.append(i)
for i in range(N+1):
    if i in edge:
        print(distance-2*min(abs(L[i]-L[i+1]),abs(L[i]-L[i-1])))
    else:
        if i == 0:
            pass
        else:
            print(distance)

### FIXED CODE ###

N = int(input())
L =[0]+ list(map(int,input().split()))+[0]
dis = 0
for i in range(N+1):
    dis += abs(L[i] - L[i+1])
#print(L,dis)
for i in range(1,N+1):
    print(dis + abs(L[i-1]-L[i+1]) - abs(L[i-1]-L[i]) - abs(L[i]-L[i+1]))
### BUGGY CODE ###

S = input()
INF = 10**9+7
dp = [0,0,0]
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N%INF
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += (dp[0]%INF)
  elif S[i]=='C':
    dp[2] += (dp[1]%INF)
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N *= 3
print(dp[2]%INF)

### FIXED CODE ###

S = input()
INF = 10**9+7
dp = [0,0,0]
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += dp[0]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N = (3*N)%INF
print(dp[2]%INF)
### BUGGY CODE ###

N = int(input())
B = list(map(int, input().split()))
A = []
s = 0
ans = 0

for i in range(N):
    A = B[:i]+B[i+1:]
    for j in range(N-1):
        ans += abs(s-A[j])
        s = A[j]
    ans += abs(A[N-2])
    print(ans)
    s = 0
    ans = 0
    A = []


### FIXED CODE ###

N = int(input())
B = list(map(int, input().split()))
A = [0] + B + [0]
s = 0
t = 0

for i in range(1,N+2):
    t += abs(s-A[i])
    s = A[i]

for i in range(1,N+1):
    print(t + abs(A[i-1]-A[i+1]) - abs(A[i-1]-A[i]) - abs(A[i]-A[i+1]))
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())

cnt = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
            cnt += gcd(i,j,m)
            

print(cnt)

### FIXED CODE ###

import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
k = int(input())
 
cnt = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
            cnt += gcd(i,j,m)
            
 
print(cnt)
### BUGGY CODE ###

def insertion(A):
  count = 0
  for i in range(1, len(A)):
    for j in range(i, 0, -1):
      if A[j] < A[j-1]:
        A[j], A[j-1] = A[j-1], A[j]
        count += 1
      else:
        break
  return count

def main():
  n = int(input())
  A = list(map(int, input().split()))
  print(insertion(A))

if __name__ == "__main__":
  main()

### FIXED CODE ###

count = 0

def merge(A, left, mid, right):
  global count
  n1 = mid - left
  n2 = right - mid
  L = A[left:left+n1]
  R = A[mid:mid+n2]
  L.append(float("inf"))
  R.append(float("inf"))
  i = 0
  j = 0
  numLeft = len(L)-1 # the number of L's elements
  for k in range(left, right):
    if R[j] < L[i]:
      A[k] = R[j]
      j += 1
      count += numLeft-i # the number of inversions to R[j]
    else:
      A[k] = L[i]
      i += 1

def mergeSort(A, left, right):
  if left + 1 < right:
    mid = int((left + right)/2)
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)


def main():
  n = int(input())
  A = list(map(int, input().split()))
  mergeSort(A, 0, n)
  print(count)

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

n = int(input())
print(0,flush=True)

prev = input()
if prev=='Vacant': exit()

now=[]

def isok(ans, odd_diff):
    print(ans,flush=True)
    now = input()

    if now == 'Vacant': exit()

    if (now!=prev and odd_diff)or(now==prev and not odd_diff):
        return True
    else:
        return False

ok = n
ng = 1
m=1
while ok - ng > 1:

    m = (ok+ng)//2
    odd_diff = ((m-ng)%2!=0)
    if isok(m, odd_diff):
        prev=now
        ok = m
    else:
        prev=now
        ng = m

print(ng)


### FIXED CODE ###

n = int(input())
print(0,flush=True)

prev = input()
if prev=='Vacant': exit()
zero = prev
now=[]

def isok(ans, odd_diff):
    print(ans,flush=True)
    now = input()

    if now == 'Vacant': exit()

    if (now==zero and odd_diff)or(now!=zero and not odd_diff):
        return True
    else:
        return False

ok = n-1 #ok以前にVacantが存在
ng = 0 #ng以前にVacantは存在しない

while ok - ng > 1:
    m = (ok+ng)//2
    odd_diff = (m%2==1)
    if isok(m, odd_diff):
        ok = m
    else:
        ng = m

print(ok,flush=True)
exit()
### BUGGY CODE ###

from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np

N,M = map(int,input().split())
#V=[[] for _ in range(N)]
row=[0]*M
col=[0]*M
data=[1]*(M)
for i in range(M):
    a,b = map(int, input().split())
    row[i]=a-1
    col[i]=b-1

s=0
graph=coo_matrix((data, (row, col)), shape=(N,N))
dist_matrix,predecessors = dijkstra(csgraph=graph, directed=False, indices = s, unweighted=True, return_predecessors=True)
#print(dist_matrix)
#print(predecessors)
print('Yes')
print(*[e+1 for e in predecessors[1:]],sep='\n')

### FIXED CODE ###

from collections import deque

N,M = map(int,input().split())
V=[[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    V[a-1].append(b-1)
    V[b-1].append(a-1)
state=[0]*N
q=deque()
ans=[0]*(N)

state[0]=1
q.append(0)
while len(q) > 0:
    v=q.popleft()
    for u in V[v]:
        if state[u]==0:
            state[u]=1
            ans[u]=v+1
            q.append(u)
print('Yes')
print(*ans[1:],sep='\n')
### BUGGY CODE ###

import functools
mod=10**9+7

def f(A):
 dem=functools.reduce(lambda x,y:x*y,range(n,n-A,-1))
 num=functools.reduce(lambda x,y:x*y,range(1,A+1))
 return dem*pow(num,mod-2,mod)%mod

n,a,b=map(int,input().split())
ans=pow(2,n,mod)-f(a)-f(b)-1
ans%=mod
print(ans)

### FIXED CODE ###

mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り
comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod
comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
def calc(ln, i):
    ans = [0]*ln
    ans[i] += i // 2 + 1
    ans[i] += (ln - i - 1) // 2
    ans[i+1] += (i + 1) // 2
    ans[i+1] += (ln-i) // 2
    return ans

left = 0
right = 0
ans = []
while left < N:
    while S[right] == "R":
        right += 1
    ind = right - 1
    while right < N and S[right] == "L":
        right += 1
    ans = ans + calc(right - left, ind-left)
    left = right
print(" ".join(map(str, ans)))

### FIXED CODE ###

S = input()
N = len(S)
def calc(ln, i):
    ans = [0]*ln
    ans[i] += i // 2 + 1
    ans[i] += (ln - i - 1) // 2
    ans[i+1] += (i + 1) // 2
    ans[i+1] += (ln-i) // 2
    print(" ".join(map(str, ans)), end=" ")

left = 0
right = 0
while left < N:
    while S[right] == "R":
        right += 1
    ind = right - 1
    while right < N and S[right] == "L":
        right += 1
    calc(right - left, ind-left)
    left = right
### BUGGY CODE ###

def main():
    A,B=map(int, input().split())
    ans={1}
    i = 2
    while (A>=i and B>=i):
        if A % i == 0 and B % i == 0:
            ans.add(i)
            A //= i
            B //= i
        else:
            i += 1
    print(len(ans))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def main():
    A,B=map(int, input().split())
    ans = factorization(gcd(A,B))
    if ans[0][0] == 1:
        print(1)
    else:
        print(len(ans)+1)

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

a = input()
total = 1 + (len(a) * (len(a) - 1) // 2)

for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] == a[j]:
            total -= 1

print(total)

### FIXED CODE ###

a = input()
total = 1 + (len(a) * (len(a) - 1) // 2)
trash = 0

for i in range(97, 97 + 26):
    atoz = (a.count(chr(i)) * (a.count(chr(i)) - 1)) // 2
    trash += atoz

print(total - trash)
### BUGGY CODE ###

import math
n, a, b = map(int, input().split())
p = 10 ** 9 + 7
#ans = 2 ** n - 1 - N C a - N C b

def modpow(a, n, MOD):
  res = 1
  while (n > 0):
    if (n & 1):
      res = res * a % MOD
    a = a * a % MOD
    n >>= 1
  return res

def cmb(n, r, p):
  A = 1
  for i in range(r):
    A *= (n - i)
    A *= modpow(i + 1, p - 2, p)
    A %= p
  return A

ans = (modpow(2, n, p) - 1) % p
ans -= cmb(n, a, p) + cmb(n, b, p)

print(ans % p)







### FIXED CODE ###

import math
n, a, b = map(int, input().split())
p = 10 ** 9 + 7
#ans = 2 ** n - 1 - N C a - N C b

def modpow(a, n, MOD):
  res = 1
  while (n > 0):
    if (n & 1):
      res = res * a % MOD
    a = a * a % MOD
    n >>= 1
  return res

def cmb(n, r, p):
  A = 1
  for i in range(r):
    A *= (n - i)
    A *= modpow(i + 1, p - 2, p)
    A %= p
  return A

ans = (modpow(2, n, p) - 1) % p
ans -= cmb(n, a, p) + cmb(n, b, p)

print(ans % p)
### BUGGY CODE ###

from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline().rstrip
show_flg=False
#show_flg=True

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(2,n+1):
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        if self.fac[n]!=0:
            return self.fac[n]
        self.fac[n]=n*self.fact(n-1)%mo
        return self.fac[n]

    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
        
ans=0

s,t=LI()
a=(2*t-s)//3
b=(2*s-t)//3
if (2*t-s)%3!=0 or (2*s-t)%3!=0:
    print(0)
    show(a,b)
    exit()

cm=Comb(a+b+1+1)
ans=cm.comb(a+b,min(a,b))
print(ans)



### FIXED CODE ###

from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline().rstrip
show_flg=False
show_flg=True

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
        
ans=0

s,t=LI()
a=(2*t-s)//3
b=(2*s-t)//3


if (2*t-s)%3!=0 or (2*s-t)%3!=0:
    print(0)
    exit()

cm=Comb(a+b+1+1)
ans=cm.comb(a+b,min(a,b))
print(ans)
### BUGGY CODE ###

n = int(input())
for i in range(1, n+1):
    count = 0
    x = 1
    while (x+1)**2 <= i-2:
        y = 1
        while x**2 + y**2 + x*y + x + y <= i-1:
            z = 1
            while x**2 + y**2 + z**2 +x*y + y*z + z*x <= i:
                if x**2 + y**2 + z**2 +x*y + y*z + z*x == i:
                    count += 1
                z += 1
            y += 1
        x += 1
    print(count)

### FIXED CODE ###

n = int(input())
ans = [0 for i in range(10050)]
for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            f = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f < 10050:
                ans[f] += 1
for i in range(n):
    print(ans[i+1])