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

s=input()
n=len(s)
v=[[0]*13 for i in range(n+1)]
v[0][0]=1
m=10**9+7
for i in range(n):
    for j in range(13):
        for k in range(10):
            x=(10*j+k)%13
            v[i+1][x]=(v[i+1][x]+(1 if s[i]=='?' or s[i]==str(k) else 0)*v[i][j])%m
print(v[n][5])


### FIXED CODE ###

s=input()
n=len(s)
v=[[0]*13 for i in range(n+1)]
v[0][0]=1
m=10**9+7
for i in range(n):
    for j in range(13):
        for k in range(10):
            x=(10*j+k)%13
            v[i+1][x]=(v[i+1][x]+(1 if s[i]=='?' or s[i]==str(k) else 0)*v[i][j])%m
print(v[n][5])
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
mod =  1000000007
ret = [0] * (N+1)
ret[0] = 1
for i in range(1,N+1):
    if i in a:
        continue
    elif i == 1:
        ret[1] = 1
    else:
        ret[i] = ret[i-2] + ret[i-1]

print(ret[len(ret)-1]%mod)


### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
mod =  1000000007
ret = [-1] * (N+1)
ret[0] = 1
for i in a:
    ret[i] = 0

for i in range(1,N+1):
    if ret[i] == 0:
        continue
    elif i == 1:
        ret[1] = 1
    else:
        ret[i] = ret[i-2] + ret[i-1]

print(ret[len(ret)-1]%mod)
### BUGGY CODE ###

import numpy as np
n=int(input())
s=input()

r=[]
g=[]
b=[]

for i in range(0,n):
    if s[i]=='R':
        r.append(i)

    elif s[i]=='G':
        g.append(i)

    elif s[i]=='B':
        b.append(i)

s=0
rl=len(r)
gl=len(g)
bl=len(b)
ml=max(rl,gl,bl)
if  ml==rl:
    d1=r
    d2=g
    d3=b
elif ml==gl:
    d1=g
    d2=r
    d3=b
else:
    d1=b
    d2=g
    d3=r

for i1 in d2:
    for i2 in d3:
        if (min(i1,i2)-np.abs(i1-i2)) in d1:
            s+=1
        if (max(i1,i2)+np.abs(i1-i2)) in d1:
            s+=1
        if (i1+i2)/2.0 in d1:
            s+=1

s2=rl*gl*bl-s
print(s2)

### FIXED CODE ###

import numpy as np
n=int(input())
s=input()

r=[]
g=[]
b=[]

for i in range(0,n):
    if s[i]=='R':
        r.append(i)

    elif s[i]=='G':
        g.append(i)

    elif s[i]=='B':
        b.append(i)

s3=0
rl=len(r)
gl=len(g)
bl=len(b)

for i in range(0,n-2):
    n2=int((n+i)/2)+1
    for j in range(i,n2):
        k=2*j-i
        if k<=n-1:
            
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                s3+=1
s2=rl*gl*bl-s3
print(s2)
### BUGGY CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,m = map(int,input().split()) #n:頂点数　w:辺の数
l=[list(map(int,input().split())) for i in range(m)]
ans=0

#d[u][v] : 辺uvのコスト(存在しないときはinf)
for j in range(m):
	d = [[float("inf") for i in range(n)] for i in range(n)]
	b=l[:j]+l[j+1:]
	for i in range(m-1):
		x,y = b[i][0],b[i][1]
		x-=1;y-=1
		d[x][y] = 1
		d[y][x] = 1
	for i in range(n):
		d[i][i] = 0 #自身のところに行くコストは０
	#print(warshall_floyd(d))
	for i in range(n):
		for k in range(n):
			if warshall_floyd(d)[i][k]==float("inf"):
				ans+=1
				break
		else:
			continue
		break
	#print(ans)
print(ans)

### FIXED CODE ###

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,w = map(int,input().split())
l=[list(map(int,input().split())) for i in range(w)]
ans=0
#edge[i] : iから出る道の[重み,行先]の配列
for j in range(w):
    edge = [[] for i in range(n)]
    b=l[:j]+l[j+1:]
    for i in range(w-1):
        x,y = b[i][0],b[i][1]
        x-=1;y-=1
        z=1
        edge[x].append([z,y]) #有向辺
        edge[y].append([z,x]) #有向辺
    if float("inf") in dijkstra_heap(0):
            ans+=1
print(ans)
### BUGGY CODE ###

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

import copy

num=[]
for i in range(n):
    num.append(int(input()))
    
for i in range(n):
    a=copy.copy(num)
    del a[i]
    print(max(a))
    

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
n = int(input()) 
num = [input() for _ in range(n)] 
num = np.array(num).astype("int64")
#ma=max(num)
#ind=num.index(ma)
sorted_num=sorted(num)
ma=sorted_num[-1]
ma2=sorted_num[-2]
for i in range(n):
    if ma != num[i]:
        print(str(ma).strip())
    else:
        print(str(ma2).strip())
### BUGGY CODE ###

import sys
input = sys.stdin.readline

S = input().rstrip()
N = len(S)
mod = 10**9+7

# dp[i][0] -> A
# dp[i][1] -> AB
# dp[i][2] -> ABC
dp = [[0, 0, 0] for _ in range(N+1)]
k = 0
for i in range(N):
    if S[i] == "A":
        dp[i+1][0] = dp[i][0] + (3**k)%mod
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "B":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1] + dp[i][0]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "C":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2] + dp[i][1]
    else:
        dp[i+1][0] = 3*dp[i][0] + (3**k)%mod
        dp[i+1][1] = 3*dp[i][1] + dp[i][0]
        dp[i+1][2] = 3*dp[i][2] + dp[i][1]
        k += 1
    
    dp[i+1][0] %= mod
    dp[i+1][1] %= mod
    dp[i+1][2] %= mod

print(dp[N][2])

### FIXED CODE ###

S = list(input())
N = len(S)
mod = int(1E9+7)

dp = [[0, 0, 0, 0] for _ in range(N+1)]

dp[N][3] = 1
for i in range(N-1, -1, -1):
    m = 3 if S[i] == '?' else 1
    dp[i][3] = m*dp[i+1][3]
    if S[i] == '?':
        dp[i][0] = m*dp[i+1][0] + dp[i+1][1]
        dp[i][1] = m*dp[i+1][1] + dp[i+1][2]
        dp[i][2] = m*dp[i+1][2] + dp[i+1][3]
    if S[i] == 'A':
        dp[i][0] = m*dp[i+1][0] + dp[i+1][1]
        dp[i][1] = m*dp[i+1][1]
        dp[i][2] = m*dp[i+1][2]
    if S[i] == 'B':
        dp[i][0] = m*dp[i+1][0]
        dp[i][1] = m*dp[i+1][1] + dp[i+1][2]
        dp[i][2] = m*dp[i+1][2]
    if S[i] == 'C':
        dp[i][0] = m*dp[i+1][0]
        dp[i][1] = m*dp[i+1][1]
        dp[i][2] = m*dp[i+1][2] + dp[i+1][3]
    dp[i][0] %= mod
    dp[i][1] %= mod
    dp[i][2] %= mod
    dp[i][3] %= mod
    
print(dp[0][0])
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    
#    print(A)
    result = 0
    for nc_len in range(1, N + 1):
        for i in range(N - nc_len + 1):
#            print(A[i : i + nc_len])
            if(sum(A[i : i + nc_len]) == 0):
                result += 1
    
    print(result)
    
if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    
    result = 0
    s = [0]
    for i in range(N):
        s.append(s[-1] + A[i])
        
    s.sort()
#    print(s)
    
    count = 1
    for i in range(N):
        if(s[i] == s[i+1]):
            count += 1
        else:
            result += count * (count -1 ) // 2
            count = 1
    result += count * (count -1 ) // 2
    print(result)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**5
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    s = sys.stdin.readline().rstrip()
    n = len(s)
    dp = [0] * (n+1)
    for i in range(n):
        for j in range(i,-1,-1):
            g = dp[j] - (1 if s[i] == 'p' else 0)
            if 0 < j <= (i+1)//2:
                p = dp[j-1] + (1 if s[i] == 'g' else 0)
            else:
                p = -INF
            dp[j] = max(g,p)
    print(dp[n//2])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**5
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    s = sys.stdin.readline().rstrip()
    n = len(s)
    ans = 0
    for i in range(n):
        if i % 2 == 0:
            if s[i] == 'p': ans -= 1
        else:
            if s[i] == 'g': ans += 1
    print(ans)

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

import numpy as np
N = int(input())
H = [int(i) for i in input().split()]

result ='Yes'
for i in range(N-1):
    num = H[i] - 1
    tmp = H[i+1:]
    if num > np.min(tmp):
        result = 'No'
        break
print(result)

### FIXED CODE ###

import numpy as np
N = int(input())
H = [int(i) for i in input().split()]

result = 'Yes'
for i in range(N-2, -1, -1):
    if H[i] - H[i+1] >= 2:
        result = 'No'
        break
    elif H[i] - H[i+1] == 1:
        H[i] -= 1
    else:
        continue
print(result)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if abs(j-i) == a[i] + a[j]:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
"""
ai + i = j - aj
"""
cnt = [0] * (n + 1)
for i in range(n):
    if 0 <= a[i] + i < n+1:
        cnt[a[i] + i] += 1

for i in range(n):
    if i - a[i] >= 0:
        ans += cnt[i - a[i]]

print(ans)
### BUGGY CODE ###

import math
K = int(input())

def gcd(a,b,c):
    return math.gcd(a, math.gcd(b,c))

s=0
for i in range(1,K+1):
    for j in range(1, K+1):
        for l in range(1, K+1):
            s += gcd(i, j, l)
print(s)

### FIXED CODE ###

from math import gcd
K = int(input())

s=0
for i in range(1,K+1):
    for j in range(1, K+1):
        for l in range(1, K+1):
            s += gcd(i, gcd(j,l))

print(s)
### BUGGY CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Chk_T,Chk_A=[False]*n,[False]*n
Max_T,Max_A=[0]*n,[0]*n
Chk_T[0],Chk_A[-1]=True,True
Max_T[0],Max_A[-1]=T[0],A[-1]

for i in range(1,n):
  if T[i]!=T[i-1]:
    Chk_T[i]=True
  Max_T[i]=T[i]
  if A[-i-1]!=A[-i]:
    Chk_A[-i-1]=True
  Max_A[-i-1]=A[-i-1]
ans=1
flag=True
for i in range(n):
  if Chk_T[i]==False and Chk_A[i]==False:
    ans=ans*min(Max_T[i],Max_A[i])
  elif Chk_T[i]==True and Chk_A[i]==False:
    if Max_T[i]>Max_A[i]:
      flag=False
  elif Chk_T[i]==False and Chk_A[i]==True:
    if Max_T[i]<Max_A[i]:
      flag=False
  else:
    if Max_T[i]!=Max_A[i]:
      flag=False
print(0 if flag==False else ans%mod)


### FIXED CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=(0,T[0])
Ares[n-1]=(0,A[n-1])
for i in range(1,n):
  if T[i]>Tres[i-1][1]:
    Tres[i]=(0,T[i])
  else:
    Tres[i]=(1,T[i])
  if A[n-i-1]>Ares[n-i][1]:
    Ares[n-i-1]=(0,A[n-i-1])
  else:
    Ares[n-i-1]=(1,A[n-i-1])
if Tres[0]<=Ares[0]:
  ans=1
else:
  ans=0
for i in range(1,n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==aa==1:
    ans=ans*min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append(["#" * W])
for h in range(H-2):
  grid.append(["#" + input() + "#"])
grid.append(["#" * W])

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    
    if grid[h][0][w]=="#": continue

    dist = [[INF]*W for i in range(H)]
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][0][n_w]=="#": continue
        d_n = d_v + 1
        if d_n > dist[n_h][n_w]:
          continue
        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))

    new_dist =[]
    for l in dist:
      new_dist.append([x for x in l if x < INF])
    LL = [max(l) if len(l)>0 else 0 for l in new_dist]
    ans = max(ans, max(LL))

print(ans)

### FIXED CODE ###

from collections import deque
import numpy as np

H,W = map(int,input().split())
maze = [input() for _ in range(H)]

ans = 0
for x in range(H):
    for y in range(W):
        #壁からはスタートできない
        if maze[x][y] == "#":
            continue

        #初期化
        distance = [[0]*W for _ in range(H)]
        #start位置
        stack = deque([[x,y]])

        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])

        #start位置は0で初期化
        distance[x][y] = 0
        ans = max(ans, np.max(distance))

print(ans)
### BUGGY CODE ###

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

mod = 1000000007

from fractions import gcd

ratios = []
nzero = 0
for a, b in ab:
    if a != 0 and b != 0:
        g = gcd(a, b)
        ratios.append((a // g, b // g))
    elif a == 0 and b == 0:
        nzero += 1
    elif a == 0:
        ratios.append((0, 1))
    else:
        ratios.append((1, 0))

twos = [1]
for i in range(2 * 10 ** 5):
    tmp = twos[-1] * 2
    tmp %= mod
    twos.append(tmp)


from collections import Counter, defaultdict
c = Counter(ratios)
seen = Counter()

targets = []
for key in c:
    x, y = key
    xx = c[key]
    if y != 0:
        yy = seen[(-y, x)] + seen[(y, -x)]
    else:
        yy = seen[(-y, x)]
    if xx != 0 and yy != 0:
        targets.append((xx, yy))
    seen[key] = c[key]

n_frees = 0
for i, (x, y) in enumerate(ratios):
    n_bads = c[(-y, x)] + c[(y, -x)]
    if n_bads == 0:
        n_frees += 1

ans = twos[n_frees]

for x, y in targets:
    ans *= (twos[x] + twos[y] - 1) % mod

print((ans - 1 + nzero) % mod)


### FIXED CODE ###

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

mod = 1000000007

from fractions import gcd

ratios = []
nzero = 0
for a, b in ab:
    if a != 0 and b != 0:
        g = gcd(a, b)
        ratios.append((a // g, b // g))
    elif a == 0 and b == 0:
        nzero += 1
    elif a == 0:
        ratios.append((0, 1))
    else:
        ratios.append((1, 0))

twos = [1]
for i in range(2 * 10 ** 5):
    tmp = twos[-1] * 2
    tmp %= mod
    twos.append(tmp)


from collections import Counter, defaultdict
c = Counter(ratios)
seen = Counter()

targets = []
for key in c:
    x, y = key
    xx = c[key]
    if y != 0:
        yy = seen[(-y, x)] + seen[(y, -x)]
    else:
        yy = seen[(-y, x)]
    if xx != 0 and yy != 0:
        targets.append((xx, yy))
    seen[key] = c[key]

n_frees = 0
for i, (x, y) in enumerate(ratios):
    n_bads = c[(-y, x)] + c[(y, -x)]
    if n_bads == 0:
        n_frees += 1

ans = twos[n_frees]

for x, y in targets:
    ans *= (twos[x] + twos[y] - 1) % mod
    ans %= mod

print((ans - 1 + nzero) % mod)
### BUGGY CODE ###

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p * p <= ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

ret = 0
for i in range(n):
    prod = 1
    for p in lcm:
        k = lcm[p] - ps[i].get(p, 0)
        prod = (prod * (p ** k)) % mod
    ret = (ret + prod) % mod

print(ret)
        


### FIXED CODE ###

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p * p <= ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

lcmv = 1
for p in lcm:
    lcmv = (lcmv * (p ** lcm[p])) % mod

def inv(p, k):
    k = mod - k - 1
    ret = 1
    b = p
    while k > 0:
        if k % 2 == 1:
            ret = (ret * b) % mod
        b = (b * b) % mod
        k //= 2
    return ret

ret = 0
for i in range(n):
    prod = lcmv
    for p in ps[i]:
        prod = (prod * inv(p, ps[i][p])) % mod
    ret = (ret + prod) % mod

print(ret)
### BUGGY CODE ###

n = int(input())
ans = n-1
for i in range(1,n//2+1):
    if n%i == 0:
        c = i+n//i-2
        if ans > c:
            ans = c
print(ans)

### FIXED CODE ###

n = int(input())
ans = n-1
for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        ans = min(ans,i+n//i-2)
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
AB = []
for i in range(H):
  AB.append(list(map(int, input().split())))

for i in range(H):
  AB[i] = [abs(AB[i][j] - int(b)) for j, b in enumerate(input().split())]

K = 80*H*W
dp = [[[False]*K for w in range(W)] for h in range(H)]
dp[0][0][abs(AB[0][0])] = True


for h in range(H):
  for w in range(W):
    if h == 0:
      if w == 0:
        continue
      else:
        for k in range(K):
          ab = AB[h][w]
          k1, k2 = abs(k - ab), k + ab
          if k1 < K and k2 < K:
            dp[h][w][k] = dp[h][w-1][k1] or dp[h][w-1][k2]
          elif k1 < K and k2 >= K:
            dp[h][w][k] = dp[h][w-1][k1]
          else:
            dp[h][w][k] = dp[h][w-1][k2]
    else:
      if w == 0:
        for k in range(K):
          ab = AB[h][w]
          k1, k2 = abs(k - ab), k + ab
          if k1 < K and k2 < K:
            dp[h][w][k] = dp[h-1][w][k1] or dp[h-1][w][k2]
          elif k1 < K and k2 >= K:
            dp[h][w][k] = dp[h-1][w][k1]
          else:
            dp[h][w][k] = dp[h-1][w][k2]
      else:
        for k in range(K):
          ab = AB[h][w]
          k1, k2 = abs(k - ab), k + ab
          if k1 < K and k2 < K:
            dp[h][w][k] = dp[h][w-1][k1] or dp[h][w-1][k2] or dp[h-1][w][k1] or dp[h-1][w][k2]
          elif k1 < K and k2 >= K:
            dp[h][w][k] = dp[h][w-1][k1] or dp[h-1][w][k1]
          else:
            dp[h][w][k] = dp[h][w-1][k2] or dp[h-1][w][k2]

for k in range(K):
  if dp[H-1][W-1][k]:
    print(k)
    break

### FIXED CODE ###

H, W = map(int, input().split())
AB = []
max_ab = 0
for i in range(H):
  AB.append(list(map(int, input().split())))
  max_ab = max(max_ab, max(AB[-1]))

for i in range(H):
  AB[i] = [abs(AB[i][j] - int(b)) for j, b in enumerate(input().split())]

base = max_ab*(H + W)
dp = [[1 << base for w in range(W)] for h in range(H)]
dp[0][0] = (1 << base + AB[0][0]) | (1 << base - AB[0][0])
for h in range(1, H):
  dp[h][0] = (dp[h-1][0] << AB[h][0]) | (dp[h-1][0] >> AB[h][0])

for w in range(1, W):
  dp[0][w] = (dp[0][w-1] << AB[0][w]) | (dp[0][w-1] >> AB[0][w])

for h in range(1, H):
  for w in range(1, W):
    dp[h][w] = (
      (dp[h-1][w] << AB[h][w]) | (dp[h-1][w] >> AB[h][w]) 
      | (dp[h][w-1] << AB[h][w]) | (dp[h][w-1] >> AB[h][w]))

positive = bin(dp[H-1][W-1] >> base)
print(positive[::-1].find('1'))
### BUGGY CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

n, k, l = map(int, input().split())
uf_road = UnionFind(n)
uf_train = UnionFind(n)

for _ in range(k):
  p, q = map(lambda x:int(x)-1, input().split())
  uf_road.Unite(p, q)

for _ in range(l):
  r, s = map(lambda x:int(x)-1, input().split())
  uf_train.Unite(r, s)

for i in range(n):
  road_member = set(uf_road.Members(i))
  train_member = set(uf_train.Members(i))
  print(len(road_member&train_member), end=" ")


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)

        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[y] = x
        else:
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def main():
  N, K, L = map(int, input().split())
  U_road = UnionFind(N)
  U_train = UnionFind(N)
  for _ in range(K):
    p, q = map(int, input().split())
    U_road.Unite(p, q)
  for _ in range(L):
    r, s = map(int, input().split())
    U_train.Unite(r, s)
  connect_dict = {}
  for i in range(1, N+1):
    x, y = U_road.Find_Root(i), U_train.Find_Root(i)
    if (x, y) in connect_dict:
      connect_dict[(x, y)] += 1
    else:
      connect_dict[(x, y)] = 1
  ans = []
  for i in range(1, N+1):
    x, y = U_road.Find_Root(i), U_train.Find_Root(i)
    ans.append(connect_dict[(x, y)])
  ans = list(map(str, ans))
  print(' '.join(ans))

  

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

#f
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)
 

n = int(input())
E = [[] for _ in range(n)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = [int(x) for x in input().split()]
    E[a-1].append((b-1, i)) 
    E[b-1].append((a-1, i)) 
    
X = [0] * n
    
def dfs(u,e):
    num = 1
    for v,c in E[u]:
        if c != e:
            num += dfs(v,c)
    X[e] = num 
    return num

dfs(0, -1)

I = [1]
for i in range(n):
    I.append(I[-1] * pow(2, mod-2, mod) % mod)

ans = 0
for i in range(n):
    x = X[i]
    ans += (1-I[x])*(1-I[n-x]) % mod
    
ans -= n * I[1]
ans += 1 - I[n]
ans %= mod
print(ans)



### FIXED CODE ###

#f
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)
 

n = int(input())
E = [[] for _ in range(n)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = [int(x) for x in input().split()]
    E[a-1].append((b-1, i)) 
    E[b-1].append((a-1, i)) 
    
X = [0] * n
    
def dfs(u,e):
    num = 1
    for v,c in E[u]:
        if c != e:
            num += dfs(v,c)
    X[e] = num 
    return num

dfs(0, -1)

I = [1]
inv = pow(2, mod-2, mod)
for i in range(n):
    I.append(I[-1] * inv % mod)

ans = 0
for i in range(n):
    x = X[i]
    ans += (1-I[x])*(1-I[n-x]) % mod
    
ans -= n * I[1]
ans += 1 - I[n]
ans %= mod
print(ans)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
answer = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    res = N-R*r-G*g
    if res >= 0 and res%B == 0:
      answer += 1
      
print(answer)
      

### FIXED CODE ###

R,G,B,N = map(int,input().split())
answer = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    res = N-R*r-G*g
    if res >= 0 and res%B == 0:
      answer += 1
      
print(answer)