Harryxun/stf_run huggingface dataset:
from collections import deque


def solve(N, K, ABs):

    Ds = [0 for _ in range(N + 1)]
    Ws = {i: [] for i in range(N + 1)}
    for a, b in ABs:
        Ws[a].append(b)
        Ws[b].append(a)

    Ds[1] = K

    s = Ws[1][0]
    Ds[s] = K - 1

    queue = deque()
    queue.append(1)
    queue.append(s)

    while queue:
        s = queue.popleft()
        k = K - 2
        for w in Ws[s]:
            if Ds[w] == 0:
                Ds[w] = k
                k -= 1
                queue.append(w)
    ans = 1
    for i in range(1, N + 1):
        if Ds[i] <= 0:
            return 0
        ans *= Ds[i]
        ans %= 1000000007
    return (ans % 1000000007)

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    print(solve(N, K, ABs))


### FIXED CODE ###

from collections import deque


def solve(N, K, ABs):
    if N == 1:
        return K

    Ds = [-1 for _ in range(N + 1)]
    Ws = {i: [] for i in range(N + 1)}
    for a, b in ABs:
        Ws[a].append(b)
        Ws[b].append(a)

    for i in range(1, N + 1):
        if Ds[i] == -1:
            Ds[i] = K

            if Ws[i]:
                s = Ws[i][0]
                Ds[s] = K - 1

                queue = deque()
                queue.append(i)
                queue.append(s)

                while queue:
                    s = queue.popleft()
                    k = K - 2
                    for w in Ws[s]:
                        if Ds[w] == -1:
                            Ds[w] = k
                            k -= 1
                            queue.append(w)

    ans = 1
    for i in range(1, N + 1):
        if Ds[i] <= 0:
            return 0
        ans *= Ds[i]
        ans %= 1000000007
    return ans % 1000000007

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    print(solve(N, K, ABs))
# coding: utf-8
n = int(input())
s = input()
if n % 2:
	print('No')
else:
	if s[0:(n/2)] == s[(n/2):n]:
		print('Yes')
	else:
		print('No')

### FIXED CODE ###

# coding: utf-8
n = int(input())
s = input()
if n % 2:
	print('No')
else:
	if s[0:int(n/2)] == s[int(n/2):n]:
		print('Yes')
	else:
		print('No')
n = int(input())
a = map(int, input().split())
ans = [0]*n

for i in range(n):
  s = a[i]
  ans[s-1] = i+1
print(*ans)

### FIXED CODE ###

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

for i in range(n):
  s = a[i]
  ans[s-1] = i+1
print(*ans)
ab = list(map(int, input().sprit()))
a = ab[0]
b = ab[1]

if (a+b)%2 == 1:
  print("IMPOSSIBLE")
  return 0

print((a+b)/2)

### FIXED CODE ###

import sys

ab = list(map(int, input().split()))
a = ab[0]
b = ab[1]

if (a+b)%2 == 1:
  print("IMPOSSIBLE")
  sys.exit(0)

print(int((a+b)/2))
n = int(input())
m = int(input())

n_dot = n*(n-1)/2
m_dot = m*(m-1)/2

answer = int(n_dot+ m_dot)
print(answer)

### FIXED CODE ###

n,m=(int(x) for x in input().split())

n_dot = n*(n-1)/2
m_dot = m*(m-1)/2

answer = int(n_dot+ m_dot)
print(answer)
a = [0]*5
for i in range(3):
  x,y = map(int,input().split())
  a[x] += 1
  a[y] += 1
if sorted(a) = [0,1,1,2,2]:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

a = [0]*5
for i in range(3):
  x,y = map(int,input().split())
  a[x] += 1
  a[y] += 1
if sorted(a) == [0,1,1,2,2]:
  print("YES")
else:
  print("NO")
N = int(input())
a = list(map(int, input().split()))


def gcd(m, n):
    if n == 0:
        return m
    else:
        return gcd(n, m % n)


def lcm(m, n):
    return (m // gcd(m, n)) * n


lc = a[0]
for i in range(N):
    lc = lcm(lc, a[i])
ans = 0
for i in range(N):
    ans += (lc // a[i])
print(int(ans % (1e9+7)))


### FIXED CODE ###

import fractions
N = int(input())
a = list(map(int, input().split()))


def lcm(m, n):
    return (m // fractions.gcd(m, n)) * n


mod = 10**9+7
lc = a[0]
for i in range(N):
    lc = lcm(lc, a[i])
ans = 0
for i in range(N):
    ans += (lc // a[i])
print(ans % mod)
N=int(input())
A=list(map(int,input().split()))
count = 0
position = 0
while position < N:
  for j in range(1,N+1):
    for i in range(position,N):
      if A[i] == j:
        count = count + 1
        break
      else:
        position = position + 1

if count != 0:
    print(N-count)
else:
    print(-1)


### FIXED CODE ###

a,b=map(int,input().split())
gcm=1
for i in range(1,1+min(a,b)):
  if a%i == 0 and b%i == 0:
    gcm = i
  else:
    gcm = gcm
    
print((a*b)//gcm)
N, K = map(int, input().split())
x = [int(i) for i in input().split()]

time = 10 ** 20
# 0以上の最小の整数
base = 0
index = 0

for i in range(N):
    if x[i] >= 0:
        base = x[i]
        index = i
        break

if index == 0:
        time = x[K-1]
else:
    for i in range(max(0, index - K), min(index, N)):
        if x[i+K-1] < 0:
            time = min(abs(x[i]), time)
        elif x[i] < 0 and  x[i+K-1] >= 0:
            time = min(min(abs(x[i]), x[i+K-1]) * 2 + max(abs(x[i]), x[i+K-1]), time)
        else:
            time = min(x[i+K-1], time)

print(time)


### FIXED CODE ###

# 無駄なところも数えて良いっていう考え方もある。
# 常に最適化しないといけないわけではない

N, K = map(int, input().split())
x = [int(i) for i in input().split()]

time = 10 ** 20

for i in range(N - K + 1):
    x_min = x[i]
    x_max = x[i + K - 1]
    if x_min >= 0:
        this_time = x_max
    elif x_max <= 0:
        this_time = abs(x_min)
    else:
        this_time = x_max - x_min + min(x_max, abs(x_min))

    if time > this_time:
        time = this_time

print(time)
"""
B - AcCepted
文字列 S が与えられます。S のそれぞれの文字は英大文字または英小文字です。 S
が次の条件すべてを満たすか判定してください。

S の先頭の文字は大文字の A である。
Sの先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1
個含まれる。
以上の A, C を除く S のすべての文字は小文字である。
"""

s = input()

ans = True
if s[0] != "A":
    ans = False
    #print("s[0] is not A")
else:
    cnt_C = 0
    for n in range(1, len(s)):
        check_char = s[n]
        
        if check_char.islower():
            pass
        else:
            if check_char == "C" and 2 <= n and n < len(s) - 1:
                cnt_C += 1
            else:
                ans = False
                break

if cnt_C != 1:
    ans = False

if ans:
    print("AC")
else:
    print("WA")

### FIXED CODE ###

"""
B - AcCepted
文字列 S が与えられます。S のそれぞれの文字は英大文字または英小文字です。 S
が次の条件すべてを満たすか判定してください。

S の先頭の文字は大文字の A である。
Sの先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1
個含まれる。
以上の A, C を除く S のすべての文字は小文字である。
"""

s = input()

cnt_C = 0
ans = True
if s[0] != "A":
    ans = False
    #print("s[0] is not A")
else:
    length = len(s)

    n = 1
    for check_char in s[1:]:
        #print(check_char)
        
        if check_char.islower() is False:
            if check_char != "C" or n == 1 or n == (length - 1):
                ans = False
            
            cnt_C += 1
        
        n += 1

if cnt_C != 1:
    ans = False

if ans:
    print("AC")
else:
    print("WA")
a,b=map(int.input(),split())
s=0
g=0
if a==1:
  s=300000
elif a==2:
  s=200000
elif a==3:
  s=100000
else:
  pass
if b==1:
  g=300000
elif b==2:
  g=200000
elif b==3:
  g=100000
else:
  pass
if a==1 and b==2:
  print(g+s+400000)
else:
  print(s+g)

### FIXED CODE ###

a,b=map(int,input().split())
s=0
g=0
if a==1:
  s=300000
elif a==2:
  s=200000
elif a==3:
  s=100000
else:
  s=0
if b==1:
  g=300000
elif b==2:
  g=200000
elif b==3:
  g=100000
else:
  g=0
if a==1 and b==1:
  print(g+s+400000)
else:
  print(s+g)
a,b,c,d,e,k= map(int, input().split())

A-B = b-a
A-C = c-a
A-D = d-a
A-E = e-a
B-C = c-b
B-D = d-b
B-E = e-b
C-D = d-c
C-E = e-c
D-E = e-d

if (A-B > k) or (A-C > k) or (A-D > k) or (A-E > k) or (B-C > k) or (B-E > k) or (C-D > k) or (C-E > k) or (D-E > k):
    print(":(")
else:
    print("Yay!")

### FIXED CODE ###

A, B = map(int, input().split())
 
C = A+B
D = A-B
E = A*B
 
LIST = [C,D,E]
 
print(max(LIST))
a = input()
return a.count("2")


### FIXED CODE ###

a = input()
print(str(a).count("2"))
a=int(input())
b=input().split(' ')
m=0
s=1
while m<a:
    s=s*int(b[m])
    m=m+1
    if s>10**18:
        print(-1)
        break

else:
    print(s)

### FIXED CODE ###

a=input().split(' ')
a[0]=int(a[0])
a[1]=int(a[1])
print(a[0]*a[1])
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[k-1])

### FIXED CODE ###

k = int(input())
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[k-1])
# coding = SJIS

a, b = map(int, input())

if a + b >= 10:
    print("error")
else:
    print(a + b)

### FIXED CODE ###

# coding = SJIS

a, b = map(int, input().split())

if a + b >= 10:
    print("error")
else:
    print(a + b)
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
INF = 1000000007

dp[0] = 1
if 1 not in a:
  dp[1] = 1
  
else:
  dp[0]= [0]

for i in range(2,n+1):
    if i not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
      dp[i] += dp[i-2] #n-2 段目が安全なら
dp[i] %= INF

print(dp[n])

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
INF = 1000000007

dp[0] = 1
if 1 not in a:
  dp[1] = 1

for i in range(2,n+1):
    if i-1 not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
    if i-2 not in a :
      dp[i] += dp[i-2] #n-2 段目が安全なら
    dp[i] %= INF

print(dp[n])
s = input()
flag = False
if "hi" in s:
    if s[s.find("hi")+2] == "i":
        flag = False
    else:
        flag = True
else:
    flag = False
    
if flag == False:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

s = input()
if s == "hi" *(len(s)//2):
    print("Yes")
else:
    print("No")
import sys
N,M,Q=map(int,input().split())
ABC=[]
ans=0
take=set([])
for i in range(Q):
  ABC+=[list(map(int,input().split()))]
ABC.sort(key=lambda x: x[3],reverse=True)
for i in range(N):
  if len(take)==N:
    print(ans)
    sys.exit
  ans+=ABC[i][3]
  take.add(ABC[i][0])
  take.add(ABC[i][1])
  take=set(take)

### FIXED CODE ###

import itertools
N,M,Q=map(int,input().split())
listA=itertools.combinations_with_replacement(range(1,M+1),N)
ans=0
listQ=[]
for q in range(Q):
  listQ+=[list(map(int,input().split()))]
for i in listA:
  anssub=0
  for a,b,c,d in listQ:
    if i[b-1]-i[a-1]==c:
      anssub+=d
  ans=max(ans,anssub)
print(ans)
def main():
    n = int(input())
    alphabets = [None] + [chr(ord("a") + x) for x in range(26)]
    # 1~26:１桁
    # 27 ~ 702(26**2*"1"+26**1*"1"+ 0):2桁
    # 27 ~ 52番：aa ~ az(26+1~26)
    # 53 ~ 78番：ba ~ bz(26*"2"+"1~26")
    # 703 ~ 18278(26+26*26+26*26*26):３桁
    # 703 ~ 726: aaa ~ aaz(26**2*"1"+26*"1"+"1~26")

    #何桁か？
    cnt = 0
    m = n
    while m > 0:
        cnt += 1
        m -= 26 ** cnt
    #print(cnt)

    # 各桁がどの文字か？
    num = []
    for i in range(cnt):
        # 最初は、26で割り、次は
        y = n % (26 ** (i+1))
        if y == 0:
          y = 26
        #print("amari:", y, "nokori:", n)
        n -= y
        num += [y // (26**i)]

    #print(num)

    ans = ""
    for s in num[::-1]:
        ans += alphabets[s]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    alphabets = [None] + [chr(ord("a") + x) for x in range(26)]
    # 1~26:１桁
    # 27 ~ 702(26**2*"1"+26**1*"1"+ 0):2桁
    # 27 ~ 52番：aa ~ az(26+1~26)
    # 53 ~ 78番：ba ~ bz(26*"2"+"1~26")
    # 703 ~ 18278(26+26*26+26*26*26):３桁
    # 703 ~ 726: aaa ~ aaz(26**2*"1"+26*"1"+"1~26")

    #何桁か？
    cnt = 0
    m = n
    while m > 0:
        cnt += 1
        m -= 26 ** cnt
    #print(cnt)

    # 各桁がどの文字か？
    num = []
    for i in range(cnt):
        # 最初は、26で割り、次は
        y = n % (26 ** (i+1))
        #print("amari:", y, "nokori:", n)
        if y == 0:
          num += [26]
          n -= 26 ** (i+1)
        else:
          n -= y
          num += [y // (26**i)]

    #print(num)

    ans = ""
    for s in num[::-1]:
        ans += alphabets[s]
    print(ans)


if __name__ == "__main__":
    main()
N, K = map(int, input().split())

array = input().split()
for i in range(len(array)):
    array[i] = int(array[i])

now = 1

history = set()
start_number = -1

for i in range(K):
    history.append(now)
    now = array[now - 1]
    if(now in history):
        start_number = now
        break

if not(start_number == -1):
    start_ind = history.index(start_number)
    length = len(history) - start_ind
    mod = (K - start_ind) % length
    now = history[start_ind + mod]

print(now)


### FIXED CODE ###

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

array = input().split()
for i in range(len(array)):
    array[i] = int(array[i])

now = 1

history = []
sethistory = set()
start_number = -1

for i in range(K):
    history.append(now)
    sethistory.add(now)
    now = array[now - 1]
    if(now in sethistory):
        start_number = now
        break

if not(start_number == -1):
    start_ind = history.index(start_number)
    length = len(history) - start_ind
    mod = (K - start_ind) % length
    now = history[start_ind + mod]

print(now)
N = int(input())
k = []
ans = 0
ans_2 = 0
for i in range(1,200):
  k.append(i)
for i in range(N):
  for j in range(N):
    if i%k[i] == 0:
      if ans == 8:
        ans_2 += 1
        break
      else:
        ans += 1
print(ans_2)

### FIXED CODE ###

N = int(input())
now = 0
ans = 0
for i in range(1,N+1):
    if i%2 == 0:
        continue
    else:
        for j in range(1,i+1):
            if i%j == 0:
                now += 1
        if now == 8:
            ans += 1
        now = 0
print(ans)
def solve(m_list):
    m_val = m_list[0]
    for i in m_list:
        m_val = min(m_val,gcd(min_val,m))
    return m_val

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

def main():
    n = int(input())
    m_list = list(map(int,input().split()))

    ans = solve(m_list)
    print(ans)

main()

### FIXED CODE ###

def solve(m_list):
    m_val = m_list[0]
    for i in m_list:
        m_val = min(m_val,gcd(m_val,i))
    return m_val

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

def main():
    n = int(input())
    m_list = list(map(int,input().split()))

    ans = solve(m_list)
    print(ans)

main()
S = input()

Dict = {}

for i in range(4):
  s = S[i]
  if s in Dict:
    Dict[s] += 1
  else:
    Dict[s]=1
if len(Dict)!=2:
  print("No")
else:
  if Dict[0]!=2 or Dict[1]!=2:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

S = input()
 
Dict = {}
 
for i in range(4):
  s = S[i]
  if s in Dict:
    Dict[s] += 1
  else:
    Dict[s]=1
    
if len(Dict)!=2:
  print("No")
else:
    List = list(Dict.values())
    if List[0]!=2 or List[1]!=2:
        print("No")
    else:
        print("Yes")
print(int(6 - int(input()) - int(input()))

### FIXED CODE ###

print(int(6 - int(input()) - int(input())))
N=int(input())
A=list(map(int,input().split()))
D=[-1]*3
ans=1
for i in A:
  c=0
  E=[]
  if i-1==D[0]:
    c+=1
    E.append(0)
  if i-1==D[1]:
    c+=1
    E.append(1)
  if i-1==D[2]:
    c+=1
    E.append(2)
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
D=[0]*3
ans=1
for i in A:
  c=0
  E=[]
  if i==D[0]:
    c+=1
    E.append(0)
  if i==D[1]:
    c+=1
    E.append(1)
  if i==D[2]:
    c+=1
    E.append(2)
  if c==0:
    print(0)
    exit()
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)
a,b,k = (int(x) for x in input().split())

if k >= a :
  if k >= b :
    if a + b >= k :
      a1 = 0
      b1 = b - k + a
    else :
      a1 = 0
      b1 = 0
  else :
    a1 = 0
    b1 = b - k + a
else :
  a1 = a - k

print(a1,b1)

### FIXED CODE ###

a,b,k = (int(x) for x in input().split())

if k >= a :
  if k >= b :
    if a + b >= k :
      a1 = 0
      b1 = b - k + a
    else :
      a1 = 0
      b1 = 0
  else :
    a1 = 0
    b1 = b - k + a
else :
  a1 = a - k
  b1 = b

print(a1,b1)
import sys
N=input()
a=[int(i) for i in input().split()]
t=0
while True:
  for i in range(N):
    if a[i]%2==0:
      a[i]//=2
      t+=1
    else:
      print(t)
      sys.exit()
      

### FIXED CODE ###

import sys
N=int(input())
a=[int(i) for i in input().split()]
t=0
while True:
  for i in range(N):
    if a[i]%2==0:
      a[i]//=2
    else:
      print(t)
      sys.exit()
  t+=1
s=input()
K=int(input())

S=[]
n=len(s)
for i in range(n):
  for j in range(i+1,n+1):
    S.append(s[i:j])
S=list(set(S))
S.sort()
print(S[K-1])

### FIXED CODE ###

s=input()
K=int(input())

S=[]
n=len(s)
for i in range(n):
  for j in range(i+1,i+K+1):
    S.append(s[i:j])
S=list(set(S))
S.sort()
print(S[K-1])
# ABC126B - YYMM or MMYY
s = input()
x, y = int(s[:2]), int(s[2:])
if x = 0 or y = 0:
    print("NA")
elif 1 <= x <= 12 and 1 <= y <= 12:
    print("AMBIGUOUS")
elif 1 <= x <= 12 and y <= 31:
    print("MMYY")
elif x <= 31 and 1 <= y <= 12:
    print("YYMM")
else:
    print("NA")

### FIXED CODE ###

# ABC126B - YYMM or MMYY
s = input()
x, y = int(s[:2]), int(s[2:])
if 1 <= x <= 12:
    if 1 <= y <= 12:
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if 1 <= y <= 12:
        print("YYMM")
    else:
        print("NA")
n=int(input())
x_str=input()
x=int(x_str,2)
x_popcount=x_str.count('1')
dp=[0]*(x_popcount+1)
for i in range(1,x_popcount+1):
    popcount=format(i,'b').count('1')
    dp[i]=dp[i%popcount]+1
# print(dp)
x_minus=x%(x_popcount-1)
x_plus=x%(x_popcount+1)
pows_minus=[(2**i)%(x_popcount-1) for i in range(n)]
pows_plus=[(2**i)%(x_popcount+1) for i in range(n)]

for i in range(len(x_str)):
    ## xi=xi mod popcount(x)+-1
    xi=0
    if x_str[i]=='1':
        xi=(x_minus-pows_minus[n-1-i])%(x_popcount-1)
    else:
        xi=(x_plus+pows_plus[n-1-i])%(x_popcount+1)
    print(dp[xi]+1)



### FIXED CODE ###

## 最初のmodをどうにか高速にやりたい → modの性質を使う
## xiのpopcount（1の数）はxのpopcount+1または-1
n=int(input())
x_str=input()
x_popcount=x_str.count('1')
dp=[0]*(x_popcount+1)
for i in range(1,x_popcount+1):
    popcount=format(i,'b').count('1')
    dp[i]=dp[i%popcount]+1
# print(dp)
# x=int(x_str,2)
if x_popcount>1:
    pows_minus=[pow(2,i,(x_popcount-1)) for i in range(n)]
    # x_minus=x%(x_popcount-1)
    x_minus=0
    for i in range(n):
        if x_str[i]=='1':
            x_minus+=pows_minus[n-1-i]
pows_plus=[pow(2,i,(x_popcount+1)) for i in range(n)]
# x_plus=x%(x_popcount+1)
x_plus=0
for i in range(n):
    if x_str[i]=='1':
        x_plus+=pows_plus[n-1-i]

for i in range(len(x_str)):
    ## xi=xi mod popcount(x)+-1
    xi=-1
    if x_str[i]=='1':
        if x_popcount>1: ## else: xi=-1
            xi=(x_minus-pows_minus[n-1-i])%(x_popcount-1)
    else:
        xi=(x_plus+pows_plus[n-1-i])%(x_popcount+1)
    if xi==-1:
        print(0)
    else:
        print(dp[xi]+1)
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy
import numpy 
 
def main():
    n = int(input())
    alist = list(map(int, input().split()))
    max_num = 10**9 + 7
    ans = 0
    for i in range(n):
        ans += numpy.cumsum(alist[:i+1])

    print(ans%max_num)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy
 

def cumsum(xs):
    pass

def main():
    n = int(input())
    alist = list(map(int, input().split()))
    max_num = 10**9 + 7
    ans = 0
    sum_num = sum(alist)

    for i in range(n-1):
        sum_num -= alist[i]
        ans += alist[i] * sum_num
        

    print(ans%max_num)

if __name__ == "__main__":
    main()
n,t=map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
d=list()
s1=0
s2=0
d=[[c[i][1]/c[i][0],c[i][0],c[i][1]] for i in range(n)]
d=sort(d,key=lamda x:(x[0],x[1]))
for i in range(n):
  s2+=d[i][2]
  s1+=d[i][1]
  if s1>=t-0.5:
    print(s2)
    exit()


### FIXED CODE ###

n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
dp=[[0]*(t+1) for i in range(n+1)]
for i in range(1,n+1):
  for j in range(t+1):
    if j!=t:
      if j-l[i-1][0]>=0:
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-l[i-1][0]]+l[i-1][1])
    else:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+l[i-1][1])
    dp[i][j]=max(dp[i-1][j],dp[i][j])
print(max(dp[n]))
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
mi = None

for i in range((H - 1) ** 2):
    # div[j] is true if row j and row j + 1 is divided
    div = [(i & (1 << j)) > 0 for j in range(H - 1)]
    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + 1 if div[j] else group[j]
    count = Counter()
    ans = div.count(True)
    ok = True
    for j in range(W):
        tmp = Counter()
        for k in range(H):
            if S[k][j] == '1':
                tmp[group[k]] += 1
        if max(tmp.values()) > K:
            ok = False
        elif max((tmp + count).values()) <= K:
            count += tmp
        else:
            count = tmp
            ans += 1
    if ok and (mi is None or ans < mi):
        mi = ans

print(mi)


### FIXED CODE ###

import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
mi = None

def _max(iterable):
    ma = 0
    for i in iterable:
        ma = max(ma, i)
    return ma

for i in range(2 ** (H - 1)):
    # div[j] is true if row j and row j + 1 is divided
    div = [(i & (1 << j)) > 0 for j in range(H - 1)]
    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + 1 if div[j] else group[j]
    count = Counter()
    ans = div.count(True)
    ok = True
    for j in range(W):
        tmp = Counter()
        for k in range(H):
            if S[k][j] == '1':
                tmp[group[k]] += 1
        if _max(tmp.values()) > K:
            ok = False
        elif _max((tmp + count).values()) <= K:
            count += tmp
        else:
            count = tmp
            ans += 1
    if ok and (mi is None or ans < mi):
        mi = ans

print(mi)
def gcd(a,b):
    if b==0:
        return a
    c=a%b
    return gcd(b,c)
x=int(input(""))
y=int(input(""))
if x<y:
    x,y=y,x
m=gcd(x,y)
print(m)
def gcd(x,y):


### FIXED CODE ###

def gcd(a,b):
    if b==0:
        return a
    c=a%b
    return gcd(b,c)
x,y=map(int,input().split())
if x<y:
    x,y=y,x
m=gcd(x,y)
print(m)
N = int(input())
A = list(map(int,input().split()))

import fractions

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

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

b = 0

for i in A:
    b += lcm_list(A)/i
print(int(b)%(10**9+7))

### FIXED CODE ###

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

import fractions

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

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

ans = A[0]
for i in range(1, N):
    ans = ans * A[i] // fractions.gcd(ans, A[i])

b = 0

for i in A:
##    b += lcm_list(A)/i
    b += ans//i
print(int(b)%(10**9+7))