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

def main():
    num, yen_sum = map(int, input().split())
    res = [-1, -1, -1]
    for bill_10000 in range(num+1):
        if bill_10000*10000 + (num-bill_10000+1)*5000 < yen_sum:
            continue
        for bill_5000 in range(num-bill_10000+1):
            if bill_10000*10000 + bill_5000*5000 + (num-bill_10000-bill_5000+1)*1000< yen_sum:
                continue
            for bill_1000 in range(num-bill_10000-bill_5000+1):
                if bill_10000*10000 + bill_5000*5000 + bill_1000*1000 == yen_sum\
                    and bill_10000 + bill_5000 + bill_1000 == num:
                    res = [bill_10000, bill_5000, bill_1000]
                    break
    print(*res)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    num, yen_sum = map(int, input().split())
    yen_sum /=1000
    res = [-1, -1, -1]
    for bill_10000 in range(num+1):
        if bill_10000*10 + (num-bill_10000+1)*5 <= yen_sum:
            continue
        for bill_5000 in range(num-bill_10000+1):
            bill_1000 = num - bill_10000 - bill_5000
            if bill_10000*10 + bill_5000*5 + bill_1000*1 == yen_sum:
                res = [bill_10000, bill_5000, bill_1000]
                break
    print(*res)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

#=====================================
class Tree():
  def __init__(self):
    self.root = None
    self.children = []
    self.counter = 0

  def add_child(self, child):
    self.children += [child]
  
  def reconstruct(self, root=None):
    if root in self.children:
      self.root = root
      self.children.remove(root)
    for child in self.children:
      child.reconstruct(self)
  
  def add_count(self, x):
    self.counter += x

  def get_count(self):
    res = self.counter
    if self.root:
      res += self.root.get_count()
    return res
      
#=====================================

def solve():
  n,q = [int(i) for i in input().split()]
  trees = [Tree() for i in range(n)]

  for _ in range(n-1):
    a,b = [int(i) for i in input().split()]
    trees[a-1].add_child(trees[b-1])
    trees[b-1].add_child(trees[a-1])

  trees[0].reconstruct()

  for _ in range(q):
    p,x = [int(i) for i in input().split()]
    trees[p-1].add_count(x)

  print(*[trees[i].get_count() for i in range(n)])

if __name__ == '__main__':
  solve()

### FIXED CODE ###

N, Q = map(int, input().split())
graph = [[] for i in range(200010)]
ans = [0 for i in range(200010)]
import sys
#sys.setrecursionlimit(100000)
sys.setrecursionlimit(10**7)
#
readline = sys.stdin.readline


for _ in range(N - 1):
    #a, b = map(int, input().split())
    a, b = map(int, readline().split())
    a -= 1
    b -= 1

    graph[a].append(b)
    graph[b].append(a)

for _ in range(Q):
    #p, x = map(int, input().split())
    p, x = map(int, readline().split())
    p -= 1

    ans[p] += x

def dfs(node, frm=-1):
    for to in graph[node]:
        if to == frm:
            continue
        ans[to] += ans[node]
        dfs(to, node)
dfs(0)

print(*ans[:N])
### BUGGY CODE ###

H,N = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

# dp[i]: 体力iにするための最小魔力
dp = [float("inf")] * (H + 1)

# 初期条件
dp[H] = 0

for i in range(H, -1, -1):
    for a, b in AB:
        HP = max(0, i - a)
        dp[HP] = min(dp[HP], dp[i] + b)

print(dp[0])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    H,N = map(int,input().split())
    AB = [[int(i) for i in input().split()] for _ in range(N)]

    dp = [float("inf")] * (H+1)

    dp[H] = 0

    for i in range(H,-1,-1):
        for j in range(N):
            tmp = max(0,i-AB[j][0])
            dp[tmp] = min(dp[tmp], dp[i]+AB[j][1])

    print(dp[0])

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

from collections import deque, defaultdict
from time import time

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]
S = time()

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if time() - S >= 1900:
        print(N * (N - 1) // 2)
        exit()
    if not isChanged:
        break

print(-1)


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')


def sol():
    N = int(input())
    A = [deque()] + [deque(map(int, input().split())) for _ in range(N)]

    days = [0] * (N + 1)
    now = [0] * (N + 1)

    que = deque([i + 1 for i in range(N)])

    while que:
        i = que.popleft()
        if not A[i]:
            continue

        a = A[i].popleft()
        if now[a] == i:
            days[a] = days[i] = max(days[a], days[i]) + 1
            que.append(i)
            que.append(a)
            now[a] = now[i] = 0
        else:
            now[i] = a

    for i in range(1, N + 1):
        if A[i]:
            print(-1)
            return
    print(max(days))


sol()
### BUGGY CODE ###

from functools import lru_cache

@lru_cache()
def get_expect(p):
    return 1.0 * (p + 1) / 2

def main():
    N, K = map(int, input().split(" "))
    P = list(map(int, input().split(" ")))

    print(max([
        sum([
            get_expect(p)
            for p in P[i:i + K]
        ])
        for i in range(N - K + 1)
    ]))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
from scipy import signal

def main():
    N, K = map(int, input().split(" "))
    P = np.array(list(map(int, input().split(" "))))

    e = (P + 1) / 2

    t = np.ones((K))

    print(np.amax(
        signal.fftconvolve(
            e,
            t
        )
    ))

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

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

def gcd(x,y):
  while y:
    x, y = y, x%y
  return x

ans = 0
for i in range(n):
  g = l[0] if i > 0 else l[1]
  for j in range(1,n):
    if j != i:
      g = gcd(g, l[j])
  ans = max(ans, g)

print(ans)

### FIXED CODE ###

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

def gcd(x,y):
  while y:
    x, y = y, x%y
  return x

ll, lr = [0]*n, [0]*n
ll[0], lr[n-1] = a[0], a[n-1]
for i in range(1,n):
  ll[i] = gcd(ll[i-1], a[i])
  lr[n-i-1] = gcd(lr[n-i], a[n-i-1])

print(max(ll[n-2], lr[1], *[gcd(l,r) for l,r in zip(ll[:n-2], lr[2:])]))
### BUGGY CODE ###

K = int(input())
a = 0
out = '-1'
for n in range(K):
  a += 7 * (10 ** n)
  if a % K == 0:
    out = n + 1
    break
print(out)

### FIXED CODE ###

K = int(input())
ans = '-1'
mod = 7%K
path = [mod]
for i in range(1,K+1):
  if mod == 0:
    ans = i
    break
  mod = (mod*10 + 7)%K
  path.append(mod)
  if mod == path[0]:
    ans = '-1'
    break
print(ans)
### BUGGY CODE ###

data=input().split()
N=int(data[0])
M=int(data[1])
data_gate=[input().split() for i in range(M)]
ans=0
for i in range(1,N+1):
    for j in range(M):
        minimum=int(data_gate[j][0])
        maximum=int(data_gate[j][1])
        if j<=M-2:
            if minimum<=i<=maximum:
                continue
            else:
                break
        else:
            if minimum<=i<=maximum:
                ans+=1
            else:
                break
print(ans)

### FIXED CODE ###

data=input().split()
N=int(data[0])
M=int(data[1])
data_gate=[input().split() for i in range(M)]
data_min=[]
data_max=[]
for i in range(M):
    data_min.append(int(data_gate[i][0]))
    data_max.append(int(data_gate[i][1]))
m=max(data_min)
M=min(data_max)
if M>=m:
    ans=M-m+1
else:
    ans=0
print(ans)
### BUGGY CODE ###

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


h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = (ch,cw)
goal = (dh,dw)
seen = [None]*n
seen[start[0]*w+start[1]] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,(ux,uy) = hpp(q)
#     print(ux,uy, num, prv)
    for xx,yy,vv in zip(dx,dy,vvs):
        x = ux+xx
        y = uy+yy
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue            
        if seen[x*w+y] is None or seen[x*w+y]>num:
            seen[x*w+y] = num
            hp(q, (num, (x,y)))
val = seen[goal[0]*w+goal[1]]
if val is None:
    print(-1)
else:
    print(val)

### FIXED CODE ###

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


h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = hpp(q)
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            hp(q, (num, u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)
### BUGGY CODE ###

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

a_list = [int(input()) for i in range(M)]

step_route = [0] * (N+1)

step_route[0] = 1
step_route[1] = 1

for j in range(N+1):  
  if j >= 2:
    step_route[j] = step_route[j-1] + step_route[j-2]
  if j in a_list:
    step_route[j] = 0
    
print(step_route[N] % 1000000007)

### FIXED CODE ###

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

step_route = [-1] * (N+1)

step_route[0] = 1
step_route[1] = 1

for i in range(M):
    tmp = int(input())
    step_route[tmp] = 0

for j in range(2,N+1):  
    if step_route[j] == -1:
        step_route[j] = step_route[j-1] + step_route[j-2]
    
print(step_route[N] % 1000000007)
### BUGGY CODE ###

S = input()

count = 0
flag = True

while flag:
    flag = False
    for i in range(len(S)-1):
        c = S.count("BW")
        count += c
        if c:
            flag = True
        S = S.replace("BW", "WB")

print(count)

### FIXED CODE ###

S = input()

count = 0

i = 0

for j in range(len(S)):
    if S[j] == "W":
        count += j-i
        i += 1


print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
res = 0
for i in range(60):
  n = len([x for x in A if x % 2 ==1])
  A = [x//2 for x in A ]
  t = 2**i
  res += n*(N-n)*t
  if all(x==0 for x in A):
    break
print(res%(7+10**9))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
res = 0
t=1
for _ in range(60):
  n = sum(x%2 for x in A)
  A = [x//2 for x in A]
  res += n*(N-n)*t
  t = t*2
  res = res%(7+10**9)
  if all(x==0 for x in A):
    break
print(res)
### BUGGY CODE ###

import math
n, m = map(int,input().split())
a = list(map(int,input().split()))
for i in range(m):
    a[a.index(max(a))] = a[a.index(max(a))]/2
for i in range(len(a)):
    a[i] = math.floor(a[i])
print(sum(a))

### FIXED CODE ###

from heapq import heappop, heappush, heapify

N, M = map(int,input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))
heapify(A)

for i in range(M):
    temp = int(heappop(A)/2)
    heappush(A, temp)

print(-sum(A))
### BUGGY CODE ###

import queue

INF = 1 << 30

s = [-1, -1]
n, s[0], s[1] = map(int, input().split())
s[0] -= 1
s[1] -= 1

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

cost = [[INF for j in range(n)] for i in range(2)]

for i in range(2):
    cost[i][s[i]] = 0
    que = queue.Queue(n)
    que.put(s[i])

    while not que.empty():
        now = que.get()
        for j in range(len(g[now])):
            if cost[i][g[now][j]] > cost[i][now] + 1:
                cost[i][g[now][j]] = cost[i][now] + 1
                que.put(g[now][j])

maxi = -1
maxdex = -1
for i in range(n):
    if len(g[i]) == 1 and maxi < cost[1][i] and cost[0][i] < cost[1][i]:
        maxi = cost[1][i]
        maxdex = i

dif = cost[1][maxdex] - cost[0][maxdex]

ans = cost[0][maxdex] + dif - 1
print(ans)

### FIXED CODE ###

import queue

INF = 1 << 30

s = [-1, -1]
n, s[0], s[1] = map(int, input().split())
s[0] -= 1
s[1] -= 1

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

cost = [[INF for j in range(n)] for i in range(2)]

for i in range(2):
    cost[i][s[i]] = 0
    que = queue.Queue(n)
    que.put(s[i])

    while not que.empty():
        now = que.get()
        for j in range(len(g[now])):
            if cost[i][g[now][j]] > cost[i][now] + 1:
                cost[i][g[now][j]] = cost[i][now] + 1
                que.put(g[now][j])

maxi = -1
maxdex = -1
for i in range(n):
    if len(g[i]) == 1 and maxi < cost[1][i] and cost[0][i] < cost[1][i]:
        maxi = cost[1][i]
        maxdex = i

dif = cost[1][maxdex] - cost[0][maxdex]

ans = cost[0][maxdex] + dif - 1
print(ans)
### BUGGY CODE ###

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

import bisect

for i in range(M):
  M = max(A)
  A.remove(M)
  x = M//2
  A.append(x)
print(sum(A))

  

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(lambda x:(-1)*int(x), input().split()))
import heapq  # heapqライブラリのimport

heapq.heapify(A)  # リストを優先度付きキューへ

# 最小値の取り出し

for i in range(M):
  heapq.heappush(A, ((-1)*heapq.heappop(A))//2*(-1))

print(sum(A)*(-1))
### BUGGY CODE ###

 # -*- coding: utf-8 -*-
import sys

def main():
	N, W = map(int, input().split(" "))
	goods = []
	for _ in range(N):
		w, v = map(int, input().split(" "))
		goods.append((w, v))
		
	DP = [[0 for _ in range(W+2)] for _ in range(N+1)]
	for i in range(N):
		w, v = goods[i]
		for w_sum in range(W+1):
			DP[i+1][w_sum] = max(DP[i+1][w_sum], DP[i][w_sum])
			if w_sum - w >= 0:
				DP[i+1][w_sum] = max(DP[i+1][w_sum], DP[i][w_sum - w] + v)
		
	print(DP[N][W])
		
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def main():
	N, W = map(int, input().split())
	wv = []
	for i in range(N):
		w, v = map(int, input().split())
		if w <= W:
			wv.append((w,v))
		
	DP = [[0 for _ in range(100001)] for _ in range(N)]
	
	for i, val in enumerate(wv):
		w, v = val
		if i == 0:
			DP[i][w] = v
			continue
			
		for j in range(W):
			DP[i][j] = max(DP[i-1][j], DP[i][j])
			
			if j+w <= W:
				DP[i][j+w] = max(DP[i-1][j] + v, DP[i][j+w])
			
	print(max(DP[N-1]))
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

n=int(input())
d=dict()
for _ in range(n):
    a=input()
    if a in d:
        d[a]+=1
    else:
        d[a]=1
keys = [k for k,v in d.items() if v==max(d.values())]
print("\n".join(sorted(keys)))

### FIXED CODE ###

from collections import Counter
n=int(input())
s=[input() for _ in range(n)]
d=Counter(s)
m=max(d.values())
keys = [k for k,v in d.items() if v==m]
print("\n".join(sorted(keys)))
### BUGGY CODE ###

import math
Q = int(input())
l_r = [list(map(int, input().split())) for _ in range(Q)]

def isprime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
def like(x):
    if isprime(x) and isprime((x+1)//2):
        return True
    
    return False

x_list = [0] * (10 ** 5)
for i in range(1, 10**5, 2):
    if like(i):
        x_list[i] = 1

for i in range(Q):
    print(sum(x_list[l_r[i][0]: l_r[i][1]+1]))

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10000000)
Q = int(input())
l_r = [list(map(int, input().split())) for _ in range(Q)]

prime = []
def isprime(n):
    if n in prime:
        return True
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    
    return True


def like(x):
    if isprime(x) and isprime((x+1)//2):
        return True
    
    return False

x_dict = {1:0}
def count_like(x):
    if x in x_dict:
        return x_dict[x]
    x_dict[x] = count_like(x-1) + like(x)
    return x_dict[x]

for i in range(Q):
    print(count_like(l_r[i][1]) - count_like(l_r[i][0]) + int(like(l_r[i][0])))
### BUGGY CODE ###

import numpy as np
from numba import njit

n=int(input())
a=np.array(list(map(int, input().split())))
b=np.array(list(map(int, input().split())))

@njit
def func():
  if np.all(a>=b):
    print(0)
  elif np.sum(a)<np.sum(b):
    print(-1)
  else:
    temp_a = a[a-b<0]
    temp_b = b[a-b<0]
    sum_a = np.sum(temp_a)
    sum_b = np.sum(temp_b)
    ans = len(temp_a)

    if sum_a>=sum_b:
      print(ans)
    else:
      aa = a[a-b>=0]
      bb = b[a-b>=0]
      for _ in range(n-ans):
        index = np.argmax(aa-bb)
        sum_a += aa[index]
        sum_b += bb[index]
        ans += 1
        if sum_a>=sum_b:
          print(ans)
          break
        else:
          aa[index]=0
          bb[index]=0
          continue
func()

### FIXED CODE ###

import sys
 
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
 
import numpy as np
 
N = int(readline())
A = np.array(readline().split(), dtype=np.int64)
B = np.array(readline().split(), dtype=np.int64)
 
diff = A-B
lack = -diff[diff<0]
remain = diff[diff>0]
 
x = lack.sum()
remain.sort()
cum = remain[::-1].cumsum()
 
y = 0 if x == 0 else np.searchsorted(cum,x) + 1
 
answer = len(lack) + y if y <= len(remain) else -1
print(answer)
### BUGGY CODE ###


def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]

    N = int(input())
    S = list(input())

    if S[0]!='B' or S[-1]!='B':
        print(0)
        exit()

    mod = 10**9 + 7
    cnt = 1
    pre = 'B'
    d = 1 #1がleft
    ans = 1

    for i in range(1,N*2):
        if S[i-1]==S[i]:
            if d:
                d = 0
                ans *= cnt%mod
                cnt -= 1
            else:
                d = 1
                cnt += 1
        else:
            if d:
                cnt += 1
            else:
                ans *= cnt%mod
                cnt -= 1

    for i in range(1,N+1):
        ans *= i
        ans %= mod
    if cnt!=0:
        print(0)
        exit()

    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import math
n = int(input())
S = input()
 
RL = [None]*2*n
 
for i in range(2*n):
    if i % 2 == 0:
        if S[i] == 'B':
            RL[i] = 'L'
        else:
            RL[i] = 'R'
 
    else:
        if S[i] == 'B':
            RL[i] = 'R'
        else:
            RL[i] = 'L'
 
if S[0] == 'W' or S[-1] == 'W':
    print(0)
    exit()
 
left = 0
count = 1
mod = 10**9 + 7
 
for check in RL:
    if check == 'L':
        left += 1
    else:
        count = count * left % mod
        left -= 1
 
    if left < 0:
        print(0)
        exit()
 
count = count * math.factorial(n) % mod
 
if left != 0:
    print(0)
else:
    print(count)
### BUGGY CODE ###

# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

N = int(input())
S = input()

pattern = []
for x in range(N):
    for y in range(x + 1, N):
        for z in range(y + 1, N):
            pattern.append(S[x] + S[y] + S[z])

print(len(set(pattern)))


### FIXED CODE ###

# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

N = int(input())
S = input()
#
# ans = 0
# pattern = []
# for x in range(N):
#     for y in range(x + 1, N):
#         if (S[x] + S[y]) not in pattern:
#             ans += len(set(S[y + 1:]))
#             pattern.append(S[x] + S[y])
#
# print(ans)
ans = 0
for i in range(1000):
    key = str(i).zfill(3)
    first = S.find(key[0])
    if first == -1 or first == N:
        continue
    second = S[first + 1:].find(key[1])
    if second == -1 or (first + second + 2) == N:
        continue
    third = S[first + second + 2:].find(key[2])
    if not third == -1:
        # print(first, first + second + 1, first + second + third + 2, key)
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
c = 1
for i in range(len(a)):
  c *= a[i]
if(c > 10 ** 18):
  print(-1)
else:
  print(c)

### FIXED CODE ###

def funct(a):
  c = 1
  if(0 in a):	return 0
  for i in range(len(a)):
    c *= a[i]
    if(c > 10 ** 18):
      return -1
  return c
n = input()
a = [int(x) for x in input().split()]
print(funct(a))
### BUGGY CODE ###

import itertools
k=int(input())
l=[[1,2,3,4,5,6,7,8,9]]
for _ in range(10):
  a=[]
  for i in range(len(l[-1])):
    L=l[-1][i]
    if L%10==9:
      a.append(L*10+8)
      a.append(L*10+9)
    elif L%10==0:
      a.append(L*10+0)
      a.append(L*10+1)
    else:
      a.append(L*10+L%10-1)
      a.append(L*10+L%10)
      a.append(L*10+L%10+1)
    l.append(a)
print(sorted(set(list(itertools.chain.from_iterable(l))))[k-1])

### FIXED CODE ###

from collections import deque
k=int(input())
l=deque([1,2,3,4,5,6,7,8,9])
for i in range(k-1):
  d=l.popleft()
  a=d%10
  if a!=0:
    l.append(d*10+a-1)
  l.append(d*10+a)
  if a!=9:
    l.append(d*10+a+1)
print(l.popleft())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

def co (i, j):
  if i == 0 or j == 0:
    return 1
  else:
    return (co(i-1, j) + co(i, j-1)) % (10**9+7) 

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]

ans = 0

if (x + y) % 3 != 0:
  ans = 0
else:
  mp = (x + y) // 3
  if min(x, y) < mp:
    ans = 0
  else:
    xi = x - mp
    yi = y - mp
    ans = co(xi, yi)

print(ans)

### FIXED CODE ###

import math

def comb(n, k, m):
  f = [1] * (n+1)
  for i in range(1, n+1):
    f[i] = f[i-1] * i % m
  return f[n] * pow_mod(f[k]*f[n-k]%m, m-2, m) % m

def pow_mod(a, b, m):
  if b == 0:
    return 1
  elif b%2 == 0:
    d = pow_mod(a, b//2, m) % m
    return d * d % m 
  else:
    d = pow_mod(a, (b-1)//2, m)
    return  d * d * a % m

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]

ans = 0
mod = 10**9 + 7

if (x + y) % 3 != 0:
  ans = 0
else:
  n = (x + y) // 3
  if min(x, y) < n:
    ans = 0
  elif min(x,y) == n:
    ans = 1
  else:
    r = min(x, y) - n
    ans = comb(n, r, mod)

print(ans)