Harryxun/stf_run huggingface dataset:
def compute_current_score(previous_t_score, previous_a_score, current_t_ratio, current_a_ratio):
    initial_divisor = max(previous_t_score // current_t_ratio, previous_a_score // current_a_ratio)
    current_t_score = 0
    current_a_score = 0
    while(True):
        current_t_score = initial_divisor * current_t_ratio
        current_a_score = initial_divisor * current_a_ratio
        if((current_t_score >= previous_t_score) and (current_a_score >= previous_a_score)):
            break
        initial_divisor += 1
    return current_t_score, current_a_score

t_list = []
a_list = []

N = int(input())
t_score, a_score = list(map(int, input().strip().split()))

for  n in range(N-1):
    t_ratio, a_ratio = list(map(int, input().strip().split()))
    t_score, a_score = compute_current_score(t_score, a_score, t_ratio, a_ratio)
    
print(t_score + a_score)

### FIXED CODE ###

inks = set(input().strip().split())
print(len(inks))
s = str(input())
N = int(s)
S = sum(list(s))
if N % S == 0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N = int(input())
s = list(str(N))
S = 0
for i in range(len(s)):
    S += int(s[i])

if N % S == 0:
    print("Yes")
else:
    print("No")
N,M=map(int,input().split())
H=list(map(int,input().split()))

ans_list=[1]*N

for i in range(M):
    a,b=map(int,input().split())
    if H[a-1]<H[b-1]:
        ans_list[a]=0
    if H[a-1]>H[b-1]:
        ans_list[b]=0
    if H[a-1]==H[b-1]:
        ans_list[a]=0
        ans_list[b]=0
print(sum(ans_list))

### FIXED CODE ###



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

ans_list=[1]*N

for i in range(M):
    a,b=map(int,input().split())
    if H[a-1]<H[b-1]:
        ans_list[a-1]=0
    if H[a-1]>H[b-1]:
        ans_list[b-1]=0
    if H[a-1]==H[b-1]:
        ans_list[a-1]=0
        ans_list[b-1]=0
print(sum(ans_list))
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))



Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
    
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)

maxval=len(Asum)-1

tmp=0
for i in range(len(Asum)):
  for j in range(len(Bsum)):
    j=tmp+j
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==len(Bsum)-1:
      maxval=max(maxval,len(Asum)-1-i+j)
      
print(maxval)

### FIXED CODE ###

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

Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
import numpy as np
Asum=np.array(Asum)
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)
Bsum=np.array(Bsum)

maxval=len(Asum)-1

tmp=0
lenB=len(Bsum)
lenA=len(Asum)
for i in range(lenA):
  if lenA-1-i+lenB<maxval:break
  for j in range(lenB):
    j=tmp+j
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==lenB-1:
      maxval=max(maxval,lenA-1-i+j)
      break
print(maxval)
N, M = [int(x) for x in input().split()]
links = [tuple(map(int, input().split())) for _ in range(M)]
S, T = [int(x) for x in input().split()]

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1

### FIXED CODE ###

N, M = [int(x) for x in input().split()]
links = [tuple(map(int, input().split())) for _ in range(M)]
S, T = [int(x) for x in input().split()]

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if h not in d or d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1
s = input()
print("Yes" if all((i%2==0 and s[i] in "RUD") or (i%2!=0 and s[i] in "LUD")) for i in range(len(s)) else "No")


### FIXED CODE ###

s=input()
print("Yes" if all((i%2==0 and s[i] in "RUD") or (i%2!=0 and s[i] in "LUD") for i in range(len(s))) else "No")
x,n = map(int,input().split())
p = list(map(int,input().split()))
if n == 0:
    print(x)
else:
    y2 = 100

    for i in range(1,max(p)+1):
        if x == i:
            continue
        if (i in p) == True:
            continue
    
        y1 = abs(i-x)
        if y2 > y1:
            y2 = y1
            t = i
    print(t)

### FIXED CODE ###

x,n = map(int,input().split())
p = list(map(int,input().split()))

if n == 0:
    print(x)

else:
    i = 1
    while True:
        t = x-i
        s = x+i
        if x not in p:
            print(x)
            break
        if t not in p:
            print(t)
            break
        if s not in p:
            print(s)
            break
        i +=1
n = int(input())
if n%2!=0:
	print('Hello Wordl')
elif:
	print(int(input())+int(input()))

### FIXED CODE ###

n=int(input())
print("Hello World" if n%2!=0 else int(input())+int(input()))
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 10000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline
from bisect import bisect_left

def dfs(i,before):
    global seq
    global ans
    added  = 0

    #現在地のAの値を、以前までのseqリストのどこに追加するか決める
    pos = bisect_left(seq,a[i-1])
    old = seq[pos]
    seq[pos]=a[i-1]
    ans[i-1]=bisect_left(seq,INF)

    #隣接する頂点に関して再帰
    for u in to[i]:
        if u==before:
            continue
        dfs(u,i)

    #seq配列をもとに戻す
    seq[pos]=old


N = I()
a = LI()
to = [[] for i in range(N+1)]
to[0] += [1]
for i in range(N-1):
    u,v = MI()
    to[u].append(v)
    to[v].append(u)
seq = [INF]*N
ans = [-1]*N

dfs(1,-1)
[print(i) for i in ans]


### FIXED CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline
from bisect import bisect_left

def dfs(i,before):
    global seq
    global ans
    added  = 0

    #現在地のAの値を、以前までのseqリストのどこに追加するか決める
    pos = bisect_left(seq,a[i-1])
    old = seq[pos]
    seq[pos]=a[i-1]
    ans[i-1]=bisect_left(seq,INF)

    #隣接する頂点に関して再帰
    for u in to[i]:
        if u==before:
            continue
        dfs(u,i)

    #seq配列をもとに戻す
    seq[pos]=old


N = I()
a = LI()
to = [[] for i in range(N+1)]
to[0] += [1]
for i in range(N-1):
    u,v = MI()
    to[u].append(v)
    to[v].append(u)
seq = [INF]*N
ans = [-1]*N

dfs(1,-1)
[print(i) for i in ans]
n=int(input())
A = list(map(int,input().split()))
for i in range(1,n+1):
    print(A.count(i))
    A.remove(i)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n-1):
  b[a[i]-1]+=1
for i in b:
  print(i)
r,D,x = map(int, input().split())

for i in range(10):
  x = r*x - D
  print(x)

### FIXED CODE ###

A,B = map(int, input().split())
 
if A < 6:
  B = 0
elif (6 <= A) and (A < 13):
  B /= 2
else :
  pass
  
print(int(B))
import sys
sys.setrecursionlimit(500000)

def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N+1)]
    for u, v, s in zip(*[iter(map(int, sys.stdin.read().split()))]*3):
        E[u].append((v, s))
        E[v].append((u, s))

    V = [[None] * (N+1), [None] * (N+1)]

    def dfs(v=1, sign=1, val=0):
        V[sign][v] = val
        sign = 1 - sign
        for u, s in E[v]:
            if V[sign][u] is None:
                dfs(u, sign, s-val)

    dfs()

    mi, ma = 1, float("inf")
    for m, p in zip(V[0][1:], V[1][1:]):
        if m is not None and p is not None:
            mp = m - p
            if mp % 2 == 0:
                a = mp // 2
                mi = max(mi, a)
                ma = min(ma, a)
            else:
                ma = -1
        if p is not None:
            mi = max(mi, 1-p)
        if m is not None:
            ma = min(ma, m-1)

    ans = max(0, ma-mi+1)

    if ans == 1:
        assert False
        A = [-1] * (N+1)
        def check(v=1, val=ma):
            A[v] = val
            for u, s in E[v]:
                if A[u] == -1:
                    check(u, s - val)
                else:
                    if A[u] != s - val:
                        print(0)
                        exit()

        check()
        #print(A)
    print(ans)

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N+1)]
    for u, v, s in zip(*[iter(map(int, sys.stdin.read().split()))]*3):
        E[u].append((v, s))
        E[v].append((u, s))

    V = [[None] * (N+1), [None] * (N+1)]

    def dfs(v=1, sign=1, val=0):
        V[sign][v] = val
        sign = 1 - sign
        for u, s in E[v]:
            if V[sign][u] is None:
                dfs(u, sign, s-val)
            else:
                if V[sign][u] != s-val:
                    print(0)
                    exit()

    dfs()

    mi, ma = 1, float("inf")
    for m, p in zip(V[0][1:], V[1][1:]):
        if m is not None and p is not None:
            mp = m - p
            if mp % 2 == 0:
                a = mp // 2
                mi = max(mi, a)
                ma = min(ma, a)
            else:
                ma = -1
        if p is not None:
            mi = max(mi, 1-p)
        if m is not None:
            ma = min(ma, m-1)

    ans = max(0, ma-mi+1)

    # if ans == 1:
    #     A = [-1] * (N+1)
    #     def check(v=1, val=ma):
    #         A[v] = val
    #         for u, s in E[v]:
    #             if A[u] == -1:
    #                 check(u, s - val)
    #             else:
    #                 if A[u] != s - val:
    #                     print(0)
    #                     exit()
    #
    #     check()
        #print(A)
    print(ans)

main()
def main():
    A, B, C, D, E, F = map(int, input().split())
    xl = []
    yl = []
    for i in range(F):
        for j in range(F):
            x = 100 * A * i + 100 * B * j
            if F >= x and x not in xl:
                xl.append(x)
    for i in range(F):
        for j in range(F):
            y = C * i + D * j
            if F >= y and y not in yl:
                yl.append(y)
    ax = float('INF')
    ay = 0
    for x in xl:
        for y in yl:
            if F >= x + y and E / (E + 100) >= y / (x + y) and y / (x + y) > ay / (ax + ay):
                ax = x
                ay = y
    print(ax + ay, ay, end=' ')


main()


### FIXED CODE ###

def main():
    A, B, C, D, E, F = map(int, input().split())
    xl = []
    yl = []
    for i in range(31):
        for j in range(31):
            x = 100 * A * i + 100 * B * j
            if F >= x and x > 0 and x not in xl:
                xl.append(x)
    for i in range(F):
        for j in range(F):
            y = C * i + D * j
            if F >= y and y > 0 and y not in yl:
                yl.append(y)
    ax = 3001
    ay = 0
    for x in xl:
        for y in yl:
            if F >= x + y and E / (E + 100) >= y / (x + y) and y / (x + y) > ay / (ax + ay):
                ax = x
                ay = y
    if ax == 3001:
        print(100 * A, 0, end=' ')
    else:
        print(ax + ay, ay, end=' ')


main()
from math import gcd
# from fractions import gcd
from functools import reduce

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

def lcm_list(numbers):
    return reduce(lambda x, y: (x * y) // gcd(x, y), numbers, 1)

lcm = lcm_list(a)
aa = []
for i in range(len(a)):
    aa.append(lcm // a[i])
ans = sum(aa) % 1000000007
print(ans)

### FIXED CODE ###

# from math import gcd
from fractions import gcd
from functools import reduce

def lcm_list(numbers):
    return reduce(lambda x, y: (x * y) // gcd(x, y), numbers, 1)

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    lcm = lcm_list(a)
    aa = []
    for i in range(len(a)):
        aa.append(lcm // a[i])
    ans = sum(aa) % 1000000007
    print(ans)

if __name__ == '__main__':
    main()
k=int(input())+1
from math import gcd
print(sum(gcd(gcd(i,j),r) for i in range(1,k)   for j in range(1,k)  for r in range(1,k) )
k=int(input())+1
from math import gcd
print(sum( gcd(gcd(i,j),r) for i in range(1,k)   for j in range(1,k)  for r in range(1,k) ))


### FIXED CODE ###

k=int(input())
from math import gcd
l=[0]*(k)
for i in range(1,k+1):
    for j in range(1,k+1):
        l[gcd(i,j)-1]+=1

ans=0
for i in range(1,k+1):
    for j in range(1,1+k):
        ans+=gcd(i,j)*l[i-1]
print(ans)
n, k = list(map(int, input().split()))

proba = 0
for i in range(1, N):
  x = i
  p = 1
  while x < K:
    p *= 0.5
    x += 1
  proba += p/N
  

### FIXED CODE ###

N, K = list(map(int, input().split()))
 
ans = 0
for i in range(1, N+1):
    p = 1
    x = i
    while x < K:
        p *= 0.5
        x *= 2
    
    ans += p/N
 
print(ans)
n,m = map(int,input().split())
arr = list(map(int,input().split()))
res = 0
for i in arr:
  if i >= m:
    res += 1
return res

### FIXED CODE ###

n=int(input())
cnt=0
for i in range(1,n+1):
    if i%2==1:
        cnt += 1
print(cnt/n)
R, G, B, N = map(int, input().split())
cnt = 0

for i in range(n // R + 1):
    for j in range(n // G + 1):
        if (N - R * i - G * j) / B >= 0 and ((N - R * i - G * j) / B) % 1 == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for i in range(N // R + 1):
    for j in range(N // G + 1):
        if (N - R * i - G * j) / B >= 0 and ((N - R * i - G * j) / B) % 1 == 0:
            cnt += 1
print(cnt)
data = input()
sec = int(data)

h = sec %= 3600
sec -= h*3600

m = sec %= 60
sec -= m*60

print('{0}:{1}:{2}'.format(h, m, s))

### FIXED CODE ###

data = input()
sec = int(data)

h = int(sec / 3600)
sec -= h*3600

m = int(sec / 60)
sec -= m*60

print('{0}:{1}:{2}'.format(h, m, sec))
import numpy as np

x,n = [int(i) for i in input().split()]
table = [int(i) for i in input().split()]
table.sort()
min = min(table)

a = np.array(table)
a = a - x
a = np.abs(a)
a = np.sort(a)
#print(a)

for i in range(n):
  if a[0] > 0:
    print(x)
    break
  elif a[i+1]-a[i]>1 and i>0:
    if a[i] > 0 and a[i] == a[i-1]:
      if x-a[i]-1 in b or x-a[i]-1 < min:
        print(x+a[i]+1)
        break
      else:
        print(x-a[i]-1)
        break
    else:
      if x-a[i] in b or x-a[i] < min:
        print(x+a[i])
        break
      else:
        print(x+a[i])
        break
      
    




### FIXED CODE ###

def main():
  x,n = [int(i) for i in input().split()]
  table = list(map(int, input().split()))
  
  for i in range(101):
    if x - i not in table:
      print(x-i)
      exit()
    elif x + i not in table:
      print(x+i)
      exit()
    	
if __name__ == "__main__":
  main()
# -*- coding: utf-8 -*-

import itertools:

while True:
 n, x = map(int, input().split())
 if n==0 and x==0: break
 count = 0
 for a, b, c in itertools.permutations(range(n), 3):
  if a+b+c==x: count += 1
 print count

### FIXED CODE ###

# -*- coding: utf-8 -*-

import itertools

while True:
 n, x = map(int, raw_input().split())
 if n==0 and x==0: break
 count = 0
 for a, b, c in itertools.combinations(range(1, n+1), 3):
  if a+b+c==x:
   count += 1
 print count
import math

s = input().split()

a = int(s[0])
b = int(s[1])
c = int(s[2])

if (a + b + 2* math.sqrt(a*b) ) < c :
  print('Yes')
else:
  print('No')

### FIXED CODE ###

d = [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]
str_n = input()
n = int(str_n)
print(d[n-1])
N = int(input())
P = list(map(int, input().split()))

dist = [P[i-1] - i for i in range(1, N+1)]

count = 0

for i in range(N):
    if dist[i] == 0:
        count += 1
        dist[i] -= 1
        dist[i+1] += 1
    elif i == N-1 and dist[i] == 0:
        count += 1
        dist[i] += 1
        dist[i-1] -= 1
        
print(count)

### FIXED CODE ###

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

dist = [P[i-1] - i for i in range(1, N+1)]

count = 0

for i in range(N):
    if dist[i] == 0:
        count += 1
        if i < N-1:
            dist[i] -= 1
            dist[i+1] += 1
        else: # i == N-1
            dist[i] += 1
            dist[i-1] -= 1
    
print(count)
n = input()
A = map(int, raw_input().split())
q = input()
M = map(int, raw_input().split())

def solve(i, m):
if m == 0:
   return True
if i >= n and m > sum(A):
   return False
res = solve(i + 1, m) or solve(i + 1, m - A[i])
return res

for m in M
   if solve(0,m):
      print 'yes'
   else:
      print 'no'

### FIXED CODE ###

n = input()
A = map(int, raw_input().split())
q = input()
M = map(int, raw_input().split())

def solve(i, m):
   if m == 0:
     return True
   if i >= n or m > sum(A):
     return False
   res = solve(i + 1, m) or solve(i + 1, m - A[i])
   return res

for m in M:
  if solve(0,m):
     print "yes"
  else:
     print "no"
n = int(input())
a = list(map(int,input().split()))

if cnt_minus % 2 == 0:
    print(sum([abs(a[i]) for i in range(n)]))
else:
    mi = min([abs(a[i]) for i in range(n)])
    print(sum([abs(a[i]) for i in range(n)]) - 2 * mi)

### FIXED CODE ###

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

cnt_minus = len([a[i] for i in range(n) if a[i] < 0])

if cnt_minus % 2 == 0:
    print(sum([abs(a[i]) for i in range(n)]))
else:
    mi = min([abs(a[i]) for i in range(n)])
    print(sum([abs(a[i]) for i in range(n)]) - 2 * mi)
#list(map(int, input().split()))
a,b,c,d=list(map(int, input().split()))
print('YES') if (g*10+b)%4==0 else print('NO')

### FIXED CODE ###

#list(map(int, input().split()))
a,b,c=list(map(int, input().split()))
print('YES') if (b*10+c)%4==0 else print('NO')
n = int(input())
list_a = list(map(int, input().split()))
num_rank = [0 for _ in range(9)]
for one_a in list_a:
  temp_rank = one_a // 400
  num_rank[temp_rank] += 1

min_color = len([i for i in num_rank[:-1] if i > 0])
max_color = len([i for i in num_rank[:-1] if i > 0]) + num_rank[-1]
print("{} {}".format(min_color, max_color))

### FIXED CODE ###

n = int(input())
list_a = list(map(int, input().split()))
num_rank = [0 for _ in range(9)]
for one_a in list_a:
  temp_rank = one_a // 400
  if temp_rank > 8:
    temp_rank = 8
  num_rank[temp_rank] += 1
if len([i for i in num_rank[:-1] if i > 0]) > 0:
  min_color = len([i for i in num_rank[:-1] if i > 0])
else:
  min_color = 1
max_color = len([i for i in num_rank[:-1] if i > 0]) + num_rank[-1]
print("{} {}".format(min_color, max_color))
N,X=map(int,input().split())
x=list(map(int,input().split()))
x=[abs(X-c) for c in x]
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
D=gcd(*x)
print(D)

### FIXED CODE ###

A,B=map(int,input().split())
if A%2==1 and B%2==1:
    print('Yes')
else:
    print('No')
n = int(input())
s = str(input())
k = int(input())
for i in range(n):
    if s[i] != s[k]:
        s = s.replace(s[i],"*")
print(s)

### FIXED CODE ###

n = int(input())
s = str(input())
k = int(input())
for i in range(n):
    if s[i] != s[k-1]:
        s = s.replace(s[i],"*")
print(s)
def solve(l):
    for i in range(l,L):
        if S[i] == '1': return 2*solve(i+1) + pow(3,L-1-i,mod) %mod
    return 1
mod = 10**9+7
S = input()
L = len(S)
print(solve(0))


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7

def solve(l):
    tmp = 0
    tmpS = ''
    for i in range(l,L):
        if S[i] == '1':
            return (2*solve(i+1) + pow(3,L-1-i,mod))%mod
    else:
        return 1

S = input()
L = len(S)
print(solve(0)%mod)
mod = 10 ** 9 + 7
def dfs(v, p, k):
    ret = 1
    if len(graph[v]) > k:
        return 0
    kc = k - 2
    if p == -1:
        kc = k - 1
    for vi in graph[v]:
        if vi != p:
            ret *= kc
            ret = ret % mod
            kc -= 1
    for vi in graph[v]:
        if vi != p:
            ret *= dfs(vi, v, k)
            ret = ret % mod
    return ret

n, k = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    
print((dfs(0, -1, k) * k) % mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(410000)

mod = 10 ** 9 + 7
def dfs(v, p, k):
    ret = 1
    if len(graph[v]) > k:
        return 0
    kc = k - 2
    if p == -1:
        kc = k - 1
    for vi in graph[v]:
        if vi != p:
            ret *= kc
            ret = ret % mod
            kc -= 1
    for vi in graph[v]:
        if vi != p:
            ret *= dfs(vi, v, k)
            ret = ret % mod
    return ret

n, k = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    
print((dfs(0, -1, k) * k) % mod)
A,B=input().split()

if A>=B*2:
  print(A-2*B)
else:
  print(0)

### FIXED CODE ###

A,B=input().split()
a=int(A)
b=int(B)
if a>=b*2:
  print(a-2*b)
else:
  print(0)