Harryxun/stf_run huggingface dataset:
h, w, k = map(int, input().split())
grid = []
for i in range(h):
    grid.append(input())

count = 0
for i in range(2**h):
    row = []
    while i:
        if i & 1:
            row.append(i & 1)
        i >>= 1
        
        for j in range(2**w):
            col = []
            while j:
                if j & 1:
                    row.append(j & 1)
                j >>= 1
            
            black = 0
            for r, c in row, col:
                if grid[r][c] == "#":
                    black += 1
            
            if black == k:
                count += 1
            
print(count)


### FIXED CODE ###

h, w, k = map(int, input().split())
grid = []
for i in range(h):
    grid.append(input())

count = 0
for i in range(2**h):
    row = []
    r = 0
    while i:
        if i & 1:
            row.append(r)
        i >>= 1
        r += 1

    for j in range(2**w):
        col = []
        c = 0
        while j:
            if j & 1:
                col.append(c)
            j >>= 1
            c += 1

        black = 0
        for r in row:
            for c in col:
                if grid[r][c] == "#":
                    black += 1

        if black == k:
            count += 1

print(count)
#!/usr/bin/env python3

# mod = 10**9+7

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

# max_digit = 61

# count_0 = [0 for _ in range(max_digit)]
# count_1 = [0 for _ in range(max_digit)]

# for i in range(len(a)):
#     num_str = bin(a[i])[2:]
#     # print(num_str)
#     for j in range(len(num_str)):
#         # print(num_str[-j-1])
#         if num_str[-j-1] == "1":
#             count_1[-j-1] += 1

# # for i in range(max_digit):
# #     count_0[i] = n-count_1[i]

# ans = 0
# count = 1
# for i in range(61):
#     # tmp = count_0[-i-1]*count_1[-i-1]
#     tmp = count_1[-i-1]*(n-count_1[-i-1])
#     ans += tmp*count
#     count = (count*2) % mod
# print(ans % mod)


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

mod = 10**9+7
max_digit = 61

ans = 0
m = 1
for _ in range(max_digit):
    bit = sum(x&m x in a)
    bit //= m
    non_bit = n - bit
    ans = (ans+bit*nonbit*m)%mod
    m <<= 1
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

# mod = 10**9+7

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

# max_digit = 61

# count_0 = [0 for _ in range(max_digit)]
# count_1 = [0 for _ in range(max_digit)]

# for i in range(len(a)):
#     num_str = bin(a[i])[2:]
#     # print(num_str)
#     for j in range(len(num_str)):
#         # print(num_str[-j-1])
#         if num_str[-j-1] == "1":
#             count_1[-j-1] += 1

# # for i in range(max_digit):
# #     count_0[i] = n-count_1[i]

# ans = 0
# count = 1
# for i in range(61):
#     # tmp = count_0[-i-1]*count_1[-i-1]
#     tmp = count_1[-i-1]*(n-count_1[-i-1])
#     ans += tmp*count
#     count = (count*2) % mod
# print(ans % mod)


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

mod = 10**9+7
max_digit = 61

ans = 0
m = 1
for _ in range(max_digit):
    bit = sum(x&m for x in a)
    bit //= m
    non_bit = n - bit
    ans = (ans+bit*non_bit*m)%mod
    m <<= 1
print(ans)
N = int(input())
r = range(N)
print(r)
l = list(r)
print(l)

if N == 1:
  print(1)
else:
  print(sum(l))

### FIXED CODE ###

N = int(input())
result = int(N*(N-1)//2)

print(result)
N = input(N)
N = N % 10
if(N == 2, 4, 5, 7, 9):
    print('hon')

elif(N == 0, 1, 6, 8):
    print('pon')

else:
    print('bon')

### FIXED CODE ###

N = int(input())
N = N % 10
if N in [2, 4, 5, 7, 9]:
    print('hon')

elif N in [0, 1, 6, 8]:
    print('pon')

else:
    print('bon')
import queue
N,u,v = map(int,input().split())
u -= 1
v -= 1
E = [[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)

ans = 0
if u==v:
    print(0)
    exit()

#u〜vの最短経路を求める
r = []
used = [False]*N
def dfs(i,end):
    global r
    used[i] = True
    if i==end:
        r.append(i)
        return True
    for e in E[i]:
        if not used[e]:
            if dfs(e,end):
                r.append(i)
                return True
    return False
dfs(v,u)

ans += (len(r)//2)+(len(r)&1)
v = r[len(r)//2]
u = r[(len(r)//2)-1]

#uから最も遠い頂点までの距離を求める
dmax = 0
used = [False]*N
def dfs2(i,end,d):
    global dmax
    used[i] = True
    if i==end:
        return
    dmax = max(dmax,d)
    for e in E[i]:
        if not used[e]:
            dfs2(e,end,d+1)
dfs2(u,v,0)
ans += dmax - 1

print(ans)

### FIXED CODE ###

N,u,v = map(int,input().split())
u -= 1
v -= 1
E = [[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)

ans = 0
if u==v:
    print(0)
    exit()

#u〜vの最短経路を求める
r = []
parent = [-1]*N
def dfs(root,end):
    global r
    stack = []
    stack.append(root)
    parent[root] = root
    while len(stack)>0:
        p = stack.pop()
        if p==end:
            break
        for e in E[p]:
            if parent[e]==-1:
                parent[e] = p
                stack.append(e)
    p=end
    while p!=root:
        r.append(p)
        p = parent[p]
    r.append(root)

dfs(v,u)
ans += (len(r)//2)+(len(r)&1)
v = r[len(r)//2]
u = r[(len(r)//2)-1]

#uから最も遠い頂点までの距離を求める
dmax = 0
depth = [-1]*N
def dfs2(root,end,d):
    global dmax
    stack = []
    stack.append(root)
    depth[root] = d
    depth[end] = 0
    while len(stack)>0:
        p = stack.pop()
        for e in E[p]:
            if depth[e]==-1:
                depth[e] = depth[p]+1
                dmax = max(dmax,depth[e])
                stack.append(e)

dfs2(u,v,0)
ans += dmax - 1

print(ans)
N,A= (int(i) for i in input().split())
a = N % 500
if (a > A):
	print("No")
else:
	print("Yes")

### FIXED CODE ###

N = int(input())
A = int(input())
if (N % 500 > A):
    print('No')
else:
    print('Yes')
def dwacon5th_prelims_b():
    n, k = (int(x) for x in input().split())
    A = [int(x) for x in input().split()]
    B = []

    for i in range(n):
        cum = 0
        for a in A[i:]:
            cum += a
            B.append(cum)
    B.sort(reverse=True)

    bit = [0]*30
    cand = B
    for i in range(30, -1, -1):
        nx = []
        for b in cand:
            if (b >> i) & 1: nx.append(b)
        if len(nx) >= k:
            cand = nx
            bit[i] = 1

    ans = int(''.join([str(x) for x in reversed(bit)]), base=2)
    print(ans)

if __name__ == '__main__':
   dwacon5th_prelims_b()

### FIXED CODE ###

def dwacon5th_prelims_b():
    n, k = (int(x) for x in input().split())
    A = [int(x) for x in input().split()]
    B = []

    for i in range(n):
        cum = 0
        for a in A[i:]:
            cum += a
            B.append(cum)
    B.sort(reverse=True)

    bit = [0]*41
    cand = B.copy()
    for i in range(40, -1, -1):
        nx = []
        for b in cand:
            if (b >> i) & 1: nx.append(b)
        if len(nx) >= k:
            cand = nx.copy()
            bit[i] = 1

    ans = int(''.join([str(x) for x in reversed(bit)]), base=2)
    print(ans)

if __name__ == '__main__':
   dwacon5th_prelims_b()
A，B，C = list(map(int, input().split()))
vincent = [A,B,C]
vincent1 = list(set(vincent))
if len(vincent1) == 2:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

A, B, C = list(map(int, input().split()))
vincent = [A,B,C]
vincent1 = list(set(vincent))
if len(vincent1) == 2:
    print("Yes")
else:
    print("No")
import math

def koch(n, x1, y1, x2, y2):
    if n == 0:
        return
  
    angle = math.radians(60)
  
    sx = (2*x1 + x2)/3
    sy = (2*y1 + y2)/3
    tx = (2*x2 + x1)/3
    ty = (2*y2 + y1)/3
    ux = (tx - sx)*math.cos(angle) - (ty - sy)*math.sin(angle) + sx
    uy = (tx - sx)*math.sin(angle) + (ty - sy)*math.cos(angle) + sy
  
    koch(n-1, x1, y1, sx, sy)
    print sx, sy
    koch(n-1, sx, sy, ux, uy)
    print ux, uy
    koch(n-1, ux, uy, tx, ty)
    print tx, ty
    koch(n-1, tx, ty, x2, y2)
  
n = input()
  
p1x = 0.0
p1y = 0.0
p2x = 100.0
p2y = 0.0
  
print p1x, p1y
kock(n, p1x, p1y, p2x, p2y)
print p2x, p2y

### FIXED CODE ###

import math
 
def koch(n, x1, y1, x2, y2):
    if n == 0:
        return
   
    angle = math.radians(60)
   
    sx = (2*x1 + x2)/3
    sy = (2*y1 + y2)/3
    tx = (2*x2 + x1)/3
    ty = (2*y2 + y1)/3
    ux = (tx - sx)*math.cos(angle) - (ty - sy)*math.sin(angle) + sx
    uy = (tx - sx)*math.sin(angle) + (ty - sy)*math.cos(angle) + sy
   
    koch(n-1, x1, y1, sx, sy)
    print sx, sy
    koch(n-1, sx, sy, ux, uy)
    print ux, uy
    koch(n-1, ux, uy, tx, ty)
    print tx, ty
    koch(n-1, tx, ty, x2, y2)
   
n = input()
   
p1x = 0.0
p1y = 0.0
p2x = 100.0
p2y = 0.0
   
print p1x, p1y
koch(n, p1x, p1y, p2x, p2y)
print p2x, p2y
visited=set()
success=1
def dfs(b,graph, node):
  global visited
  if node not in visited:
    visited.add(node)
    for counter in range(len(graph[node-1][0])):
      if b[graph[node-1][0][counter]-1]==10000000000000000000:
        b[graph[node-1][0][counter]-1]=b[node-1]+graph[node-1][1][counter]
      else:
        if  b[graph[node-1][0][counter]-1]!=b[node-1]+graph[node-1][1][counter]:
          global success
          success=0
      dfs(b,graph, graph[node-1][0][counter])
n,m=map(int,input().split())
a=[]
b=[10000000000000000000]*n
for i in range(n):
  a.append([[],[]])
done=[0]*n
for i in range(m):
  l,r,d=map(int,input().split())
  a[l-1][0].append(r)
  a[l-1][1].append(d)
  a[r-1][0].append(l)
  a[r-1][1].append(-d)
current=[1]
for i in range(n):
  b=[10000000000000000000]*n
  b[i]=0
  dfs(b,a,i+1)
if success==0:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

visited=set()
success=1
import sys
sys.setrecursionlimit(1000000)
def dfs(graph, node):
  global visited
  global b
  global success
  if node not in visited:
    visited.add(node)
    for counter in range(len(graph[node-1][0])):
      if b[graph[node-1][0][counter]-1]==10000000000000000000:
        b[graph[node-1][0][counter]-1]=b[node-1]+graph[node-1][1][counter]
      else:
        if  b[graph[node-1][0][counter]-1]!=b[node-1]+graph[node-1][1][counter]:
          success=0
      dfs(graph, graph[node-1][0][counter])
      
n,m=map(int,input().split())
a=[]
b=[10000000000000000000]*n
for i in range(n):
  a.append([[],[]])
done=[0]*n
for i in range(m):
  l,r,d=map(int,input().split())
  a[l-1][0].append(r)
  a[l-1][1].append(d)
  a[r-1][0].append(l)
  a[r-1][1].append(-d)
current=[1]
for i in range(n):
  if i+1 in visited:
    continue
  b[i]=0
  dfs(a,i+1)
if success==0:
  print('No')
else:
  print('Yes')
a = list(map(int, input().split()))
b = list(map(int, input().split()))
t = int(input())
aw = a[0]+a[1]*t
bw = b[0]+b[1]*t
diff = a[1]-b[1] # 1秒ごとに縮まる
adiff = b[0] - a[0] # 元々の差
count = 0
if int(adiff/diff) <= t:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

a = list(map(int, input().split()))
b = list(map(int, input().split()))
t = int(input())
diff = (a[1]-b[1])*t # 1秒ごとに縮まる
adiff = abs(a[0]-b[0]) # 元々の差
if diff >= adiff:
  print('YES')
else:
  print('NO')
ans = 0
cnt_s = cnt_t = 0

for c in s:
    if c == 'S':
        cnt_s += 1
    else:
        cnt_t += 1
    if cnt_t > cnt_s:
        ans += cnt_s
        cnt_s = cnt_t = 0
ans += cnt_s
print(len(s) - ans*2)

### FIXED CODE ###

s = input().rstrip()

removed = 0
cnt_s = cnt_t = 0

for c in s:
    if c == 'S':
        cnt_s += 1
    else:
        cnt_t += 1
    if cnt_t > cnt_s:
        removed += cnt_s
        cnt_s = cnt_t = 0
#     print(cnt_s,cnt_t)
removed += min(cnt_s,cnt_t)
print(len(s) - removed*2)
N = int(input())
A = [0] * 100005
for i in range(N):
    a = int(input())
    A[a] = 1 - A[a]
ans = 0
for i in range(100005):
    ans += A[i]
print(ans)


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)
A.sort()
ans = 0
cnt = 1
for i in range(N-1):
    if A[i] == A[i + 1]:
        cnt += 1
        continue
    ans += cnt % 2
    cnt = 1
if cnt % 2 == 1:
    ans += 1
print(ans)
#include<stdio.h>

int main(){
  
  	int N, summ, i;
  	i = 1;
  	summ = 0;
  
  	scanf("%d", &N);
  
  	while(i <= N){
    	if (N%3==0||N%5==0){
        	summ = summ;
        }
      	else{
        	summ += i;
        }
      	i++;
    }
  
  	printf("%d", summ);
	return 0;
}

### FIXED CODE ###

n = input()
n = str(n)
count = 0
 
for i in n:
  if (i=='7'):
    count = 1
    break
    
if (count!=0):
	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]) % int(1e9+7)
    ans %= int(1e9+7)
print(int(ans))


### 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())
S = str(input())
p = "abc"
print(N.count(p))

### FIXED CODE ###

N = int(input())
S = str(input())
S = S.replace("ABC","ab")
print(N - len(S))
n = int(input())
sum=0
for i in range(n):
    sum += int(input())
print(sum-n)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
print(sum(a)-n)
a,b = int(input().split())

print(a*b)

### FIXED CODE ###

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

print(a[0]*a[1])
a , b , x = map(int , input().split())

#1度傾けると何㎝水が進むか
angle_1 = b / 90

#水の高さ
l_water = b - ((a**2 * b) - x) / a ** 2

#残りの高さ
l_Remaining = b - l_water

#角度
angle = l_Remaining / angle_l

print(angle)

### FIXED CODE ###

import math

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

area_base = a ** 2
volum_bottle = area_base * b

k = (2 * (volum_bottle - x)) / a ** 2

if k <= b:
  K_t = k / a
  angle = math.degrees(math.atan(K_t))
else:
  L_t = a * (b ** 2) / (2 * x)
  angle = math.degrees(math.atan(L_t))
  
print(round(angle, 10))
import math
r = int(input())
print("%f %f" % (2 * r * math.pi, r ** 2 * math.pi))

### FIXED CODE ###

import math 
a=float(input())
b=a*math.pi
print(a*b,2*b)
n = raw_input()
A = map(int, raw_input().split())
d = {}
 
def solution(i, m, n):
    if m == 0:
        return True
    if i >= n:
        return False
    if d.has_key((i, m)):
        return d[(i, m)]
    res = solution(i + 1, m, n) or solution(i + 1, m - A[i], n)
    d[(i, m)] = res
    return res
 
 
q = raw_input()
M = map(int, raw_input().split())
for m in M:
    if solution(0, m, n):
        print 'yes'
    else:
        print 'no'

### FIXED CODE ###

def ans(n, AA, x):
    tmp = n + AA[0]
    if len(AA) == 1:
        try: x[tmp] = 1
        except: pass
    else:
        ans(n, AA[1:], x)
        try:
            x[tmp] = 1
            ans(tmp, AA[1:],x)
        except:
            pass
    return
 
n = raw_input()
A = map(int, raw_input().split())
q = raw_input()
M = map(int, raw_input().split())
 
x = [0 for i in range(max(M)+1)]
ans(0, A, x)
 
for e in M:
    if x[e] == 1:
        print 'yes'
    else:
        print 'no'
import copy
N = int(input())

L = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

ans = []

def f(List):
    if sum(List) == N:
        List.sort(reverse=True)
        s = ""
        for i in range(10):
            s += L[i]*List[i]
        ans.append(s)
    for i in range(9):
        if List[i+1] == 0:
            n = List[i]
            idx = i+1
            break
    for i in range(1, min(n, N-sum(List))+1):
        List2 = copy.copy(List)
        List2[idx] = i
        f(List2)

for i in range(1, N+1):
    List = [0]*10
    List[0] = i
    f(List)

ans.sort()
for a in ans:
    print(a)

### FIXED CODE ###

N = int(input())

L = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

ans = []
def f(List, n):
    if n == N:
        s = ""
        for l in List:
            s += L[l]
        ans.append(s)
        return None
    for i in range(max(List)+2):
        f(List+[i], n+1)

f([0], 1)        
ans.sort()
for a in ans:
    print(a)
x=input()
if 400<=x and x<600:
 rank=8
elif 600<=x and x<800:
  rank=7
elif 800<=x and x<1000:
  rank=6
elif 1000<=x and x<1200:
  rank=5
elif 1200<=x and x<1400:
  rank=4
elif 1400<=x and x<1600:
  rank=3
elif 1600<=x and x<1800:
  rank=2
elif 1800<=x and x<2000:
  rank =1
print(rank)


### FIXED CODE ###

x=input()
x=int(x)
if x>=400 and x<600:
  rank=8
elif 600<=x and x<800:
  rank=7
elif 800<=x and x<1000:
  rank=6
elif 1000<=x and x<1200:
  rank=5
elif 1200<=x and x<1400:
  rank=4
elif 1400<=x and x<1600:
  rank=3
elif 1600<=x and x<1800:
  rank=2
elif 1800<=x and x<2000:
  rank =1
print(rank)
k,n=map(input(),int.split())
a=map(list(input(),int.split()))

m=0
for i in range(n-1):
    d=a[i+1]-a[i]
    m=max(d,m)
d_last=a[0]+k-a[n-1]
m=max(d_last,m)

ans=k-m
print(ans)

### FIXED CODE ###

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

m=0
for i in range(n-1):
    d=a[i+1]-a[i]
    m=max(d,m)
d_last=a[0]+k-a[n-1]
m=max(d_last,m)

ans=k-m
print(ans)
n = int(input())
A = list(map(int, input().split()))
mod=int(1e9+7)

memo={}
for a in A:
  memo[a]=memo.get(a,0)+1

answer=1
if n%2:
  if memo[0]!=1:
    print(0)
    exit()
  for i in range(1, (n+1)//2):
    if memo[2*i]!=2:
      print(0)
      exit()
    else:
      answer = 2*answer %mod
elif not n%2:
  for i in range(n//2):
    if memo[2*i+1]!=2:
      print(0)
      exit()
    else:
      answer = 2*answer %mod
      
print(answer)
      
    


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
mod=int(1e9+7)

memo={i:0 for i in range(n)}
for a in A:
  memo[a]=memo.get(a,0)+1

answer=1
if n%2:
  if memo[0]!=1:
    print(0)
    exit()
  for i in range(1, (n+1)//2):
    if memo[2*i]!=2:
      print(0)
      exit()
    else:
      answer = 2*answer %mod
elif not n%2:
  for i in range(n//2):
    if memo[2*i+1]!=2:
      print(0)
      exit()
    else:
      answer = 2*answer %mod
      
print(answer)
a = int(input())
b = int(input())
  
print(str(a*b)+" "+str(2a + 2b))

### FIXED CODE ###

z = input()
m,l = z.split()
s = int(m) * int(l)
n = int(m)*2 + int(l)*2

print("{} {}".format(str(s),str(n)))
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    a, b, c, k = list(map(int, readline().split()))
    s = [1] * a + [0] * b + [-1] * c
    print(s)
    ans = sum(s[:k])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    a, b, c, k = list(map(int, readline().split()))
    if a + b >= k:
        print(min(a, k))
    else:
        print(a - (k - a - b))


if __name__ == '__main__':
    main()
num = int(input())
Flag = False
for x in range(2,10):
    for y in range(x,10):
        print("x"+str(x)+":y"+str(y))
        if x * y == num:
            Flag = True
            break
    if Flag == True:
        break

if Flag:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

num = [int(_) for _ in input().split(" ")]
if 0<num[0]<10 and 0<num[1]<10:
  print(num[0]*num[1])
else:
  print(-1)
def fact(i):
    a = 1
    for i in range(2,i+1):
        a *= i
    return a
def comb(i,j):
    if j != 0 and j != i
        return int(fact(i)/(fact(j)*fact(i-j)))
    else:
        return 1

n = int(input())
l = list(map(int,input().split()))
l.sort()
a = []
b = []
d = []
for i in range(1,n):
    c = l[i]
    if l[0] >= int((c+1)/2):
        a.append(comb(c,l[0]))
        b.append(c)
        d.append(l[0])
    else:
        j = 0
        while l[j] < int((c+1)/2):
            j += 1
        else:
            if l[j] == int((c+1)/2):
                a.append(comb(c,int((c+1)/2)))
                b.append(c)
                d.append(int((c+1)/2))
            else:
                if l[j] - int((c+1)/2) < int((c+1)/2) -l[j-1]:
                    a.append(comb(c,l[j]))
                    b.append(c)
                    d.append(l[j])
                else:
                    a.append(comb(c,l[j-1]))
                    b.append(c)
                    d.append(l[j-1])
I = a.index(max(a))
print("{} {}".format(b[I],d[I]))


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort()
a = l[-1]
j = 0
while l[j] < int((a+1)/2):
    j += 1
else:
    if l[j] - int((a+1)/2) < int((a+1)/2) - l[j-1]:
        b = l[j]
    else:
        b = l[j-1]
print("{} {}".format(a,b))
from math import gcd
def lcm(i, j):
  return i * j // gcd(i, j)
def main():
  while True:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p, q, r, b = lst[n]
      if weight[n] != -1: pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p, q)
      elif r == 0:
        setWeight(b)
        l = lcm(weight[b] * q, p)
        weight[n] = l // q + l // p
      elif b == 0:
        setWeight(r)
        l = lcm(weight(r) * p, q)
        weight[n] = l // p + l // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        l = lcm(weight[r] * p, weight[b]  * q)
        weight[n] = l // p + l // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0, n):
      if weight[i + 1] == -1:
        setWeight(i + 1)
    print(max(weight))

if __name__ == '__main__':
  main()



### FIXED CODE ###


from math import gcd
def lcm(i, j):
  return i * j // gcd(i, j)
def main():
  while True:
    n = int(input())
    if not n: break
    lst = [[]]
    weight = [-1 for i in range(n + 1)]
    def setWeight(n):
      p, q, r, b = lst[n]
      if weight[n] != -1: pass
      elif r == 0 and b == 0:
        weight[n] = (p + q) // gcd(p, q)
      elif r == 0:
        setWeight(b)
        l = lcm(weight[b] * q, p)
        weight[n] = l // q + l // p
      elif b == 0:
        setWeight(r)
        l = lcm(weight[r] * p, q)
        weight[n] = l // p + l // q
      else:
        if weight[r] == -1: setWeight(r)
        if weight[b] == -1: setWeight(b)
        l = lcm(weight[r] * p, weight[b]  * q)
        weight[n] = l // p + l // q
    for i in range(n):
      lst.append(list(map(int,input().split())))
    for i in range(0, n):
      if weight[i + 1] == -1:
        setWeight(i + 1)
    print(max(weight))

if __name__ == '__main__':
  main()
R,G,B,N = map(int,input().split(" "))

from math import gcd

C = G * B // gcd(G,B)

s = 0
b = 0
while b <= N:
    bb = b
    while bb <= N:
        if (N - bb) % B == 0:
            s += (N - bb) // C + 1
            bb = N + 1
        else:
            bb += G
    b += R

print(s)

### FIXED CODE ###

def gcd(n,m):
    while n > 0:
        a = n
        n = m % n
        m = a
    return m

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

C = G * B // gcd(G,B)

s = 0
b = 0
while b <= N:
    bb = b
    while bb <= N:
        if (N - bb) % B == 0:
            s += (N - bb) // C + 1
            bb = N + 1
        else:
            bb += G
    b += R

print(s)
N = int(input())
C = [-1]

prev = -1
for _ in range(N):
    c = int(input())
    if c == prev:
        continue
    else:
        C.append(c)
        prev = c

MOD = 10**9+7
n = len(C)
dp = [0]*(n+1)
last = [-1]*(N+N)
dp[0] = 1
for i in range(1, n+1):
    if last[C[i]] == -1:
        last[C[i]] = i
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1]+dp[last[C[i]]]
        dp[i] %= MOD
        last[C[i]] = i
print(max(dp))


### FIXED CODE ###

N = int(input())
C = [-1]

for _ in range(N):
    c = int(input())
    if c == C[-1]:
        continue
    else:
        C.append(c)

MOD = 10**9+7
dp = 1
prev = [0]*(max(C)+1)

for c in C[1:]:
    dp = (dp+prev[c]) % MOD
    prev[c] = dp
print(dp)