Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

#N=10**5
#mod=10**8
#import random
#EDGE=[[i,random.randint(1,i-1)] for i in range(2,N+1)]

EDGELIST=[[] for i in range(N+1)]
DPDICT=dict()

for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

for i in range(1,N+1):
    if len(EDGELIST)==1:
        DPDICT[(i,EDGELIST[i][0])]=2    


def SCORE(point):
    ANS=1
    for to in EDGELIST[point]:
        ANS=ANS*dp(to,point)%mod
    return ANS

def dp(x,y):
    if DPDICT.get((x,y))!=None:
        return DPDICT[(x,y)]

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    DPDICT[(x,y)]=ANS+1
    return ANS+1

for i in range(1,N+1):
    print(SCORE(i))

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

if N==1:
    print(1)
    sys.exit()

EDGELIST=[[] for i in range(N+1)]
for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

SCORELIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST_rev=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
EDICT=dict()

for i in range(1,N+1):
    for j in range(len(EDGELIST[i])):
        EDICT[(i,EDGELIST[i][j])]=j

def dp(x,y):
    if SCORELIST[y][EDICT[(y,x)]]!=-1:
        return SCORELIST[y][EDICT[(y,x)]]

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1   
    return ANS+1

def dp2(x,y):
    if PRODLIST[x][0]==-1:
        PRODLIST[x][0]=(SCORELIST[x][0])%mod
        for i in range(1,len(EDGELIST[x])):
            PRODLIST[x][i]=PRODLIST[x][i-1]*SCORELIST[x][i]%mod

        PRODLIST_rev[x][-1]=SCORELIST[x][-1]
        for i in range(len(EDGELIST[x])-2,-1,-1):
            PRODLIST_rev[x][i]=PRODLIST_rev[x][i+1]*SCORELIST[x][i]%mod

    if len(EDGELIST[x])==1:
        ANS=1
    elif EDICT[(x,y)]==0:
        ANS=PRODLIST_rev[x][1]
    elif EDICT[(x,y)]==len(EDGELIST[x])-1:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]
    else:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]*PRODLIST_rev[x][EDICT[(x,y)]+1]%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1

for to in EDGELIST[1]:
    dp(to,1)

QUE=deque([1])
check=[0]*(N+1)

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue
    for to in EDGELIST[x]:
        if check[x]==0 or check[to]==0:
            dp2(x,to)
            QUE.append(to)
    check[x]=1

for i in range(1,N+1):
    print(PRODLIST[i][-1])
import sys
import copy
input = sys.stdin.readline

def main():
  s = input()
  n = len(s)
  x, y = map(int, input().split())
  
  x_max = 0
  y_max = 0
  dpx = [[False, False] for _ in range(n+1)]
  dpy = [[False, False] for _ in range(n+1)]

  dpx[0][0] = True
  dpy[0][0] = True
  x_turn = False
  y_turn = False
  judge = True
  turn = False
  xcount = 0
  count = 0
  for i in range(n):
    if judge and s[i] == "F":
      xcount += 1
      continue
    if judge:
      judge = False
      turn = False if turn else True
      continue
    if s[i] == "F":
      count += 1
      if i != n-1:
        continue
    if turn:
      y_turn = False if y_turn else True
      if y_turn:
        p, q = 0, 1
      else:
        p, q = 1, 0
      for i in range(n+1):
        
        dpy[i][q] = False
      for i in range(n+1):
        if dpy[i][p]:
          dpy[abs(i-count)][q] = True
          dpy[i+count][q] = True
        if i == y_max:
          y_max = i+count
          break
    else:
      x_turn = False if x_turn else True
      if x_turn:
        p, q = 0, 1
      else:
        p, q = 1, 0
      for i in range(n+1):
        dpx[i][q] = False
      for i in range(n+1):
        if dpx[i][p]:
          dpx[abs(i-count)][q] = True
          dpx[i+count][q] = True
        if i == x_max:
          x_max = i+count
          break
    turn = False if turn else True
    count = 0
  
  p = 1 if x_turn else 0
  q = 1 if y_turn else 0
  x -= xcount
  if dpx[abs(x)][p] and dpy[abs(y)][q]:
    print("Yes")
  else:
    print("No")
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  s = input()
  n = len(s)
  x, y = map(int, input().split())

  dpx = [[False, False] for _ in range(n+2)]
  dpy = [[False, False] for _ in range(n+2)]

  dpx[0][0] = True
  dpy[0][0] = True
  x_turn = False
  y_turn = False
  judge = True
  turn = False
  xcount = 0
  count = 0
  for i in range(n):
    if judge and s[i] == "F":
      xcount += 1
      continue
    if judge:
      judge = False
      turn = False if turn else True
      continue
    if s[i] == "F":
      count += 1
      if i != n-1:
        continue
    if turn:
      y_turn = False if y_turn else True
      if y_turn:
        p, q = 0, 1
      else:
        p, q = 1, 0
      for i in range(n+1):
        
        dpy[i][q] = False
      for i in range(n+1):
        if dpy[i][p]:
          dpy[abs(i-count)][q] = True
          dpy[i+count][q] = True
    else:
      x_turn = False if x_turn else True
      if x_turn:
        p, q = 0, 1
      else:
        p, q = 1, 0
      for i in range(n+1):
        dpx[i][q] = False
      for i in range(n+1):
        if dpx[i][p]:
          dpx[abs(i-count)][q] = True
          dpx[i+count][q] = True
    turn = False if turn else True
    count = 0
  
  p = 1 if x_turn else 0
  q = 1 if y_turn else 0
  x -= xcount
  if abs(x) > n:
    print("No")
  elif dpx[abs(x)][p] and dpy[abs(y)][q]:
    print("Yes")
  else:
    print("No")
  
if __name__ == "__main__":
  main()
N,K = map(int,input().split())
P = list(map(int,input().split()))
Q = []*N
for i in range(N):
  Q[i] = (P[i]+1)/2
R = sum(Q[:K])
ans = R
for j in range(N-K):
  R = R - Q[j] + Q[j+K]
  ans = max(ans,R)
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
  P[i] = (P[i]+1)/2
now = sum(P[:K])
ans = now
for j in range(N-K):
  now = now - P[j] + P[j+K]
  ans = max(ans,now)
print(ans)
n,m=map(int,input().split())

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

def DFS(x):
    global no_checked
    global xyz
    no_checked[x-1]=1
    for item in xyz[x]:
        if no_checked[item-1]==0:
            DFS(item)

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        DFS(i)

    #print(i,no_checked)
print(cnt)



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n,m=map(int,input().split())

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

def DFS(x):
    global no_checked
    global xyz
    no_checked[x-1]=1
    for item in xyz[x]:
        if no_checked[item-1]==0:
            DFS(item)

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        DFS(i)

    #print(i,no_checked)
print(cnt)
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0221

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def fb_gen(count=1):
    while True:
        if count % 15 == 0:
            ans = 'FizzBuzz'
        elif count % 5 == 0:
            ans = 'Buzz'
        elif count % 3 == 0:
            ans = 'Fizz'
        else:
            ans = str(count)
        yield ans
        count += 1


def main(args):
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break
        players = deque(range(1, m+1))
        fb = fb_gen()
        for _ in range(n):
            p = input().strip()
            if p != fb.__next__():
                try:
                    drop = players.popleft()
                except:
                    players = deque(drop)
                if len(players) == 1:
                    break
            else:
                players.rotate(-1)

        result = list(players)
        result.sort()
        print(*result)


if __name__ == '__main__':
    main(sys.argv[1:])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0221

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def fb_gen(count=1):
    while True:
        if count % 15 == 0:
            ans = 'FizzBuzz'
        elif count % 5 == 0:
            ans = 'Buzz'
        elif count % 3 == 0:
            ans = 'Fizz'
        else:
            ans = str(count)
        yield ans
        count += 1


def main(args):
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break
        players = deque(range(1, m+1))
        fb = fb_gen()
        ok_count = 0
        for _ in range(n):
            p = input().strip()
            if p != fb.__next__():
                if len(players) > 1:
                    players.rotate(ok_count)
                    players.popleft()
                    ok_count = 0
            else:
                ok_count -= 1

        result = list(players)
        result.sort()
        print(*result)


if __name__ == '__main__':
    main(sys.argv[1:])
N,Q = map(int,input().split())
AB = [[int(i) for i in input().split()] for _ in range(N-1)]
PX = [[int(j) for j in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
counters = [0] * (N+1)
for p,x in PX:
    counters[p] += x
    
def dfs(v,parent,add):
    counters[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,counters[v])

dfs(1,0,0)

ans = ' '.join(map(str,counters[1:]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(i) for i in input().split()] for _ in range(N-1)]
PX = [[int(j) for j in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
counters = [0] * (N+1)
for p,x in PX:
    counters[p] += x
    
def dfs(v,parent,add):
    counters[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,counters[v])

dfs(1,0,0)

ans = ' '.join(map(str,counters[1:]))
print(ans)
n, k = map(int, input().split())
p = [int(x) for x in input().split()]

M = 0
for i in range(k):
    M += (1 + p[i]) / 2

e = M
for i in range(n-k):
    e -= (1 + p[i]) / 2
    e += (1 + p[i+k]) / 2
    if e > M:
        M = e
print('{%.12f}'.format(M))

### FIXED CODE ###

n, k = map(int, input().split())
p = [int(x) for x in input().split()]

M = 0
for i in range(k):
    M += (1 + p[i]) / 2

e = M
for i in range(n-k):
    e -= (1 + p[i]) / 2
    e += (1 + p[i+k]) / 2
    if e > M:
        M = e
print('{:.12f}'.format(M))
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
cost=[0,2,5,5,4,5,6,3,7,6]
inf=-1*float("inf")
dp=[inf]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for j in range(m):
        dp[i]=max(dp[i],dp[i-cost[a[j]]]+1)
ans=[]
for i in range(dp[n]):
    for j in range(m):
        if dp[n-cost[a[j]]]==dp[n]-1:
            ans.append(a[j])
            n-=cost[a[j]]
            break
print("".join(list(map(str,ans))))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
nums=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for x in a:
        if i-nums[x]>=0:
            dp[i]=max(dp[i-nums[x]]+1,dp[i])
k=dp[n]
ans=[]
for i in range(k):
    for x in a:
        if n-nums[x]<0:
            continue
        if dp[n-nums[x]]==dp[n]-1:
            n-=nums[x]
            ans.append(x)
            break
print("".join(list(map(str,ans))))
n = input()
n = n/3
a = n**3
print(a)

### FIXED CODE ###

n = int(input())
n = n/3
a = n**3
print(a)
N,M=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(M)]

f=[[] for _ in range(N+1)]
for i in range(M):
    f[s[i][0]].append(s[i][1])

found=[0 for _ in range(N+1)]
ans=0

def find(bi,i,root,found):
    if root[i]:
        return
    root[i]=1
    found[i]=1
    f[i].append(bi)
    for j in range(len(f[i])):
        find(i,f[i][j],root,found)

for i in range(1,N+1):
    if found[i]: continue
    root=[0 for _ in range(N+1)]
    find(i,i,root,found)
    tmp=root.count(1)
    if ans<tmp:
        ans=tmp
print(ans)


### FIXED CODE ###

from collections import deque

N,M=map(int,input().split())
G=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

group=[]
seen=[0]*N
ans=0
for i in range(N):
    if seen[i]: continue
    que=deque()
    seen[i]=1
    cnt=0
    que.append(i)
    while que:
        cnt+=1
        v=que.popleft()
        for nv in G[v]:
            if seen[nv]: continue
            seen[nv]=1
            que.append(nv)
    ans=max(ans,cnt)

print(ans)
a, b, k = map(int, input().split())

for i in range(k):
  if a > 0:
    a -= 1
  elif b > 0:
    b -= 1
  else:
    beak

print('{} {}'.format(a, b))

### FIXED CODE ###

a, b, k = map(int, input().split())
 
if a > k:
  print('{} {}'.format(a - k, b))
elif a + b > k:
  print('0 {}'.format(a + b - k))
else:
  print('0 0')
import collections
def main():
    n = int(input())
    a = list(map(int,input().split()))
    cnt = collections.Counter(a)
    num = len(set(a))
    aset=set(a)
    a1, a2, a3 = aset
    if sum(a) == 0:
        print('Yes')
        return
    # if n % 3 != 0:
        # print('No')
        # return
    if len(cnt.most_common()) == 3:
        if cnt.most_common()[0][1] == cnt.most_common()[1][1] == cnt.most_common()[2][1]  and a1 ^ a2 == a3:
            # print(cnt.most_common())
            print('Yes')
            return

    if len(cnt.most_common()) == 2:

        tmp_min = cnt.most_common()[1][1]
        tmp_max = cnt.most_common()[0][1]
        if 3 * tmp_min == n and int(cnt.most_common()[1][0]) == 0:
            print('Yes')
            return
    print('No')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections
def main():
    n = int(input())
    a = list(map(int,input().split()))
    cnt = collections.Counter(a)
    num = len(set(a))
    aset=set(a)

    if sum(a) == 0:
        print('Yes')
        return
    # if n % 3 != 0:
        # print('No')
        # return
    if len(cnt.most_common()) == 3:
        a1, a2, a3 = aset
        if cnt.most_common()[0][1] == cnt.most_common()[1][1] == cnt.most_common()[2][1]  and a1 ^ a2 == a3:
            # print(cnt.most_common())
            print('Yes')
            return

    if len(cnt.most_common()) == 2:

        tmp_min = cnt.most_common()[1][1]
        tmp_max = cnt.most_common()[0][1]
        if 3 * tmp_min == n and int(cnt.most_common()[1][0]) == 0:
            print('Yes')
            return
    print('No')

if __name__ == '__main__':
    main()
import sys

n,m = map(int,input().split())
sc = []

for _ in range(m):
  sc.append(list(map(int,input().split())))

sc.sort()

if n == 1:
  print(sc[0][1])
  sys.exit()
if sc[0][0] == 1 and sc[0][1] == 0:
  print('-1')
  sys.exit()

ans = [-1 for _ in range(n)]
for i in range(m):
  if ans[sc[i][0]-1] == -1:
    ans[sc[i][0]-1] = sc[i][1]
  else:
    if ans[sc[i][0]-1] != sc[i][1]:
      print('-1')
      sys.exit()

res = ''
if ans[0] == 0:
  ans[0] = 1
for i in range(n):
  if ans[i] == -1:
    ans[i] = 0
  res = res + str(ans[i])

print(res)


### FIXED CODE ###

import sys

n,m = map(int,input().split())
sc = []

if m == 0 and n == 1:
  print(0)
  sys.exit()
elif m == 0 and n != 1:
  print(10**n // 10)
  sys.exit()


for _ in range(m):
  sc.append(list(map(int,input().split())))

sc.sort()

if n == 1:
  tmp = 0
  for i in range(m):
    if sc[i][0] == 1 and sc[i][1] == 0:
      tmp += 1
    if tmp == m:
      print(0)
      sys.exit()

if sc[0][0] == 1 and sc[0][1] == 0:
  print('-1')
  sys.exit()

ans = [-1 for _ in range(n)]
for i in range(m):
  if ans[sc[i][0]-1] == -1:
    ans[sc[i][0]-1] = sc[i][1]
  else:
    if ans[sc[i][0]-1] != sc[i][1]:
      print('-1')
      sys.exit()

res = ''
if ans[0] == -1:
  ans[0] = 1
for i in range(n):
  if ans[i] == -1:
    ans[i] = 0
  res = res + str(ans[i])

print(res)
N = int(input())
List = dict()
for i in range(N):
    X,L = map(int,input().split())
    List.update({X:L})
keys= sorted(List)
if len(List)<=1:
    print(len(List))
elif len(List)<3:
    if keys[0]+List[keys[0]]>keys[1]-List[keys[1]] or keys[1]-List[keys[1]]<keys[0]+List[keys[0]]:
        del List[keys[i]]
    print(len(List))
else:
    for i in range(1, len(keys)-1):
        if keys[i]+List[keys[i]]>keys[i+1]-List[keys[i+1]] or keys[i]-List[keys[i]]<keys[i-1]+List[keys[i-1]]:
            print(keys,keys[i],List[keys[i]],keys[i+1])
            del List[keys[i]]
    print(len(List))


### FIXED CODE ###

n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
nl=[]
for i in range(n):
  nl.append([l[i][0]+l[i][1],l[i][0]-l[i][1]])
nl.sort()
if n==1:
  print(1)
else:
  ans=1
  k=nl[0][0]
  for i in range(1,n):
    if k<=nl[i][1]:
      ans+=1
      k=nl[i][0]
  print(ans)
X = int(input())
m = 100
y = 0
while True:
    if X <= m: break
    m = math.floor(m * 1.01)
    y += 1
print(y)


### FIXED CODE ###

import math

X = int(input())
m = 100
y = 0
while True:
    if X <= m: break
    m = math.floor(m * 1.01)
    y += 1
print(y)
n=int(input())
if(n==3):
  print("No")
elif(n%4==0 or n%4==3):
  print("Yes"):
else:
  print("No")

### FIXED CODE ###

import sys
n=int(input())
if(n%7==0):
  print("Yes")
  sys.exit(0)
while(1):
    if(n%4==0):
        print("Yes")
        sys.exit(0)
    n-=7
    if(n<=3):
        break
print("No")
def A(w, v, n,V):
    mem=[0 for i in range(V+1)]
    if n == 0 or V == 0:
        return 0

    for i in range(n):
        for j in range(V,W[i]-1,-1):
            mem[j] = max(mem[j], v[i]+ mem[j - w[i]])
    return mem[V]
n,V=input().split()
n,V=int(n),int(V)

w=[0]*n
v=[0]*n
for i in range(n):
  x,y=input().split()
  w[i],v[i]=int(x),int(y)

print(A(W,V,4,4))


### FIXED CODE ###

def A(w, v, n,V):
    mem=[0 for i in range(V+1)]
    if n == 0 or V == 0:
        return 0
 
    for i in range(n):
        for j in range(V,w[i]-1,-1):
            m=v[i]+ mem[j - w[i]]
            if m>mem[j]:
                mem[j]=m
    return mem[V]
n,V=input().split()
n,V=int(n),int(V)
 
w=[0]*n
v=[0]*n
for i in range(n):
  x,y=input().split()
  w[i],v[i]=int(x),int(y)
 
print(A(w,v,n,V))
import math
def func(x):
    return math.pi*2*x
x=R  
print(func(x))

### FIXED CODE ###

import math
n=int(input())
def func(n):
    return math.pi*n*2
print(func(n))
from itertools import combinations
s=input()
ans=0
for i in range(len(s)):
    for j in combinations(range(1,len(s)),i):
        c=0
        s_i=s
        for k in j:
            s_i=s_i[:k+c]+"+"+s_i[j+c:]
            c+=1
        ans+=eval(s_i)
print(ans)


### FIXED CODE ###

s=input()
count=0
for i in range(2**(len(s)-1)):
    t=""
    for j in s:
        t+=j
        if i%2==1:
            t+="+"
        i//=2
    count+=eval(t)
print(count)
import collections

def solve(n, points):
    a = []
    for i in range(n-1):
        for j in range(i + 1, n):
            x = points[i][0] - points[j][0]
            y = points[i][1] - points[j][1]
            if x > 0:
                a.append((x, y))
            elif x < 0:
                a.append((-x, -y))
            else:
                a.append((0, abs(y)))

    c = collections.Counter(a).most_common()[0][1]
    return n - c

n = int(input())
points = [list(map(int, input().split(' '))) for _ in range(n)]
print(solve(n, points))



### FIXED CODE ###

import collections

def solve(n, points):
    if n == 1:
        return 1
    a = []
    for i in range(n-1):
        for j in range(i + 1, n):
            x = points[i][0] - points[j][0]
            y = points[i][1] - points[j][1]
            if x > 0:
                a.append((x, y))
            elif x < 0:
                a.append((-x, -y))
            else:
                a.append((0, abs(y)))

    c = collections.Counter(a).most_common()[0][1]
    return n - c

n = int(input())
points = [list(map(int, input().split(' '))) for _ in range(n)]
print(solve(n, points))
from math import factorial
 
s = int(input())
 
ans = 0
for i in range(s // 3):
    box = i + 1  # 箱の数
    ball = s - 3 * box # あらかじめ箱に３こずつ入れたあとの残りの玉の数
 
　　# 箱の入れ方が何通りあるか計算。
    # 割り算を // ではなく / とするとfloat型の計算となりオーバーフローする可能性がある。
    # factorial(s_ + i) // (factorial(s_) * factorial(i))ではなくfactorial(s_ + i) // (factorial(s_) // factorial(i))としても同様にオーバーフローする可能性がある。
    ans_ = factorial(ball + box - 1) // (factorial(ball) * factorial(box - 1)) % (10**9 + 7)
    ans += ans_
print(ans)

### FIXED CODE ###

s = int(input())

x = s // 3

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

ans = 0
for i in range(x):
    Box = i + 1
    Nokori = s - 3 * Box
    ans_ = cmb(Nokori + Box - 1, Box - 1) 
    ans += ans_
print(ans % (10 ** 9 + 7))
import numpy as np
# 行数
N,D = input().strip().split()
N = int(N)
D = int(D)
# 2次元配列
grid = []
for i in range(N):
    array = list(map(int, input().strip().split()))
    grid.append(array)
    
count = 0
for i in range(0,N):
  dist = sqrt(grid[i][0]^2+grid[i][1]^2)
  if dist <= D:
    count += 1
print(count)

### FIXED CODE ###

import numpy as np
N,D = input().strip().split()
N = int(N)
D = int(D)
count = 0
for i in range(N):
    x,y = input().strip().split()
    x = int(x)
    y = int(y)
    #print(x**2)
    dist = np.sqrt((x)**2+(y)**2)
    #print(dist)
    if dist <= D:
        count +=1
print(count)
D = int(input())

if D == 25:
 print("Christmas")
else if D == 24:
 print("Christmas Eve")
else if D== 23:
 print("Christmas Eve Eve")
else:
 print("Christmas Eve Eve Eve")

### FIXED CODE ###

d = int(input())

if d == 25:
  print("Christmas")
elif d == 24:
  print("Christmas Eve")
elif d == 23:
  print("Christmas Eve Eve")
else:
  print("Christmas Eve Eve Eve")