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

import sys

H,W = list(map(int, input().split()))
S = [[]]*H

for h in range(H):
    S[h] = input()

T = [None]*W

for w in range(W):
    t = [S[h][w] for h in range(H)]
    T[w] = ''.join(t)

#print(S)
#print(T)


def calc_lights_map(MAP, H, W):
    LIGHTS_MAP = [None]*H
    for h in range(H):
        lights_map_row = calc_lights_map_row(MAP[h], W)
        LIGHTS_MAP[h] = lights_map_row
    return LIGHTS_MAP


def calc_lights_map_row(ROW, W):
    lights_map_row = []
    lights = 0
    for here, masu in enumerate(ROW):
        if masu == '#':
            lights_map_row.append(0)
            lights = 0
            continue
        if lights > 0:
            lights_map_row.append(lights)
            continue
        try:
            wall_id = ROW.index('#', here)
        except:
            wall_id = len(ROW)
        lights = wall_id - here
        lights_map_row.append(lights)
        continue
    return lights_map_row

S_lights_map = calc_lights_map(S, H, W)

#print(S)
#print(S_lights_map)

T_lights_map = calc_lights_map(T, W, H)

#print(T)
#print(T_lights_map)


max_lights = 0
for h in range(H):
    for w in range(W):
        lights = S_lights_map[h][w] + T_lights_map[w][h] - 1
        max_lights = max(max_lights, lights)


print(max_lights)


### FIXED CODE ###

import sys

H,W = list(map(int, input().split()))
S = [[]]*H

for h in range(H):
    S[h] = input()

T = [None]*W

for w in range(W):
    t = [S[h][w] for h in range(H)]
    T[w] = ''.join(t)

#print(S)
#print(T)


def calc_lights_map(MAP, H, W):
    LIGHTS_MAP = [None]*H
    for h in range(H):
        lights_map_row = calc_lights_map_row(MAP[h], W)
        LIGHTS_MAP[h] = lights_map_row
    return LIGHTS_MAP


def calc_lights_map_row(ROW, W):
    lights_map_row = []
    lights = 0
    for here, masu in enumerate(ROW):
        if masu == '#':
            lights_map_row.append(0)
            lights = 0
            continue
        if lights > 0:
            lights_map_row.append(lights)
            continue
        try:
            wall_id = ROW.index('#', here)
        except:
            wall_id = len(ROW)
        lights = wall_id - here
        lights_map_row.append(lights)
        continue
    return lights_map_row

S_lights_map = calc_lights_map(S, H, W)

#print(S)
#print(S_lights_map)

T_lights_map = calc_lights_map(T, W, H)

#print(T)
#print(T_lights_map)


max_lights = 0
for h in range(H):
    for w in range(W):
        lights = S_lights_map[h][w] + T_lights_map[w][h] - 1
        max_lights = max(max_lights, lights)


print(max_lights)
### BUGGY CODE ###

n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
squares = []
for i in range(len(xy)):
    x1 = xy[i][0]
    for j in range(i+1,len(xy)):
        x2 = xy[j][0]
        for m in range(len(xy)):
            y1 = xy[m][1]
            for l in range(m+1,len(xy)):
                y2 = xy[l][1]
                square = (min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2))
                squares.append(square)
ans = float('inf')
for x1,x2,y1,y2 in squares:
    if x1==x2 or y1==y2:
        continue
    points = 0
    for x,y in xy:
        if x1<=x<=x2 and y1<=y<=y2:
            points+=1
    if points==k:
        ans = min(ans,(x2-x1)*(y2-y1))
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
x_y = [list(map(int,input().split())) for _ in range(n)]
x_y = sorted(x_y,key=lambda x:(x[0],x[1]))
ans = float('inf')
for i in range(n-1):
    for j in range(i+1,n):
        if j-i+1<k:
            continue
        dis_x = x_y[j][0]-x_y[i][0]
        y_x = x_y[i:j+1]
        y_x = sorted(y_x,key=lambda x:x[1])
        for l in range(len(y_x)-1):
            for m in range(l+1,len(y_x)):
                if m-l+1<k:
                    continue
                dis_y = y_x[m][1]-y_x[l][1]
                ans = min(ans,dis_x*dis_y)
print(ans)
### BUGGY CODE ###

N=int(input())
import copy
inp=[]
for i in range(N):
    inp.append(list(map(int,input().split(" "))))

def compare(A,B):
    if A[0]>=B[0] and A[1]>=B[1]:
        return A
    else:
        A0=copy.copy(A[0])
        A1=copy.copy(A[1])
        while A0<B[0] or A1<B[1]:
            A0+=A[0]
            A1+=A[1]
        return [A0,A1]
st=inp[0]
for i in range(1,N):
    st=compare(inp[i],st)
print(sum(st))

### FIXED CODE ###

N=int(input())
import copy
inp=[]
for i in range(N):
    inp.append(list(map(int,input().split(" "))))

def compare(A,B):
    if A[0]>=B[0] and A[1]>=B[1]:
        return A
    else:
        if B[0]%A[0]!=0:
            i=B[0]//A[0]+1
        else:
            i=B[0]//A[0]
        if B[1]%A[1]!=0:
            j=B[1]//A[1]+1 
        else:
            j=B[1]//A[1]
        m=max(i,j)
        return [A[0]*m,A[1]*m]
st=inp[0]
for i in range(1,N):
    st=compare(inp[i],st)
print(sum(st))
### BUGGY CODE ###

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

result = 0

def dfs(num, dem, k, cur_num, p, q, a, n):
    global result
    #print num, dem, k, cur_num
    #time.sleep(0.5)
    if (num * q) == (dem * p):
        result += 1
        #print "result: " + str(result)
        return

    if k == n:
        return

    if (num * q) > (dem * p):
        return

    i = cur_num
    while i * dem <= a:
        dfs((num * i) + dem, dem * i, k + 1, i, p, q, a, n)
        i += 1

    return

def func():
    while True:
        global result
        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        result = 0
        dfs(0, 1, 0, 1, p, q, a, n)
        print result
        
    return None

if __name__ == '__main__':
    func()
    

### FIXED CODE ###

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

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        if num * i < dem:
            i += 1
            continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

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

n = int(input())
p = list(map(int,input().split()))
miss = 0
for i in range(n):
    s = p[0:i]
    s = sorted(s,reverse=True)
    #print(s)
    for j in range(i):
        if p[i] > s[j]:
            miss += 1
            break

print(n-miss)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
cnt = 0
t = p[0]

for i in range(n):
    if t >= p[i]:
        cnt += 1
        t = p[i]


print(cnt)
### BUGGY CODE ###

S = str(input())
Q = int(input())

qs = [list(map(str, input().split())) for _ in range(Q)]

def addFirst(base, s):
    return s + base

def addLast(base, s):
    return base + s

def reverse(base):
    return ''.join(list(reversed(base)))

for ls in qs:
    if ls[0] == "1":
        S = reverse(S)
    else:
        if ls[1] == "1":
            S = addFirst(S, ls[2])
        else:
            S = addLast(S, ls[2])

print(S)

### FIXED CODE ###

S = str(input())
Q = int(input())

qs = [list(map(str, input().split())) for _ in range(Q)]

x, y = S, ""
for ls in qs:
    if ls[0] == "1":
        x, y = y, x
    else:
        if ls[1] == "1":
            y += ls[2]
        else:
            x += ls[2]
            
y = ''.join(list(reversed(y)))
print(y+x)
### BUGGY CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
base = []
ans2=0
for n in range(K, N+1):
    ans1=ans2
    start = n-K
    ans = 1
    for a in As[start:n]:
        ans *= a
    ans2 = ans
    if n != K:
        if ans1 < ans2:
            print("Yes")
        else:
            print("No")

### FIXED CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
ans2=0
for n in range(K+1, N+1):
    ans1 = As[n-K-1]
    ans2 = As[n-1]
    if ans1 < ans2:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n,k = map(int,input().split())
if(k==1):
  print(0)
else:
  while(len(str(n))>1):
    n = n/2
  t = n//k
  for i in range(t):
    n = abs(n-k)
  if(n < abs(k-n)):
    print(n)
  else:
    print(abs(k-n))

### FIXED CODE ###

N, K = map(int,input().split())
t = N%K
if (K - t) >= t:
    print(t)
else:
    print(K - t)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
i=0
ans =0

while i<n:
    if p[i]==i+1:
        ans += 1
        i+=1
    if not (i==n-2 and p[i+1]==i+2):
        i += 1
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
i=0
ans =0
while i<n-1:
    if p[i]==i+1:
        p[i], p[i+1] = p[i+1], p[i]
        ans += 1
    i+=1
if p[n-1]==n:
    ans+=1
print(ans)
### BUGGY CODE ###

MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

def sol():
    K = int(input())
    S = input()
    N = len(S)

    comb = Combination(N + K + 100)

    ans = 0
    L = 1
    R = pow(26, K, MOD)
    inv26 = comb.inv[26]
    for l in range(K + 1):
        ans += L * comb.nhr(N, l) * R
        ans %= MOD

        L = L * 25 % MOD
        R = R * inv26 % MOD

    print(ans)
sol()

### FIXED CODE ###

MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

K = int(input())
S = input()
N = len(S)

comb = Combination(N + K + 100)

ans = 0
for l in range(K + 1):
    r = K - l
    ans += pow(25, l, MOD) * comb.nhr(N, l) * pow(26, r, MOD)
    ans %= MOD

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

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

num = 1
for i in range(1, N):
    if min(P[:i]) >= P[i]:
        num += 1
    else:
        num = num

print(num)

### FIXED CODE ###

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

ans = 0
curMin = 1e9
for i in range(N):
    curMin = min(curMin, P[i])
    if curMin == P[i]:
        ans += 1

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

#!/usr/bin/env python3
import math

def main():
    N = int(input())
    T, A = map(int, input().split())
    for _ in range(N-1):
        t, a = map(int, input().split())
        tmpT, tmpA = t,a
        while 1:
            if T <= tmpT and A <= tmpA:
                T,A = tmpT, tmpA
                break
            else:
                tmpT += t
                tmpA += a
    print(T+A)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import math

def main():
    N = int(input())
    T, A = map(int, input().split())
    for _ in range(N-1):
        t, a = map(int, input().split())
        # 桁が大きいとfloatの誤差が生じて正しく判定できない
        # 負の数にして切り捨てにすればceilと同じ挙動になる
        x = max(-(-T//t), -(-A//a))
        T = t*x
        A = a*x
    print(T+A)

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

N = int(input())
L = [int(i) for i in input().split()]
from itertools import combinations
ans = 0
for a,b,c in combinations(L,3):
    if a < b+c and b < a+c and c < a+b:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
L = sorted([int(i) for i in input().split()])
from bisect import bisect_left
ans = 0
for i1,a in enumerate(L):
    L_temp = L[i1+1:]
    for i2,b in enumerate(L_temp):
        L_temp2 = L_temp[i2+1:]
        #print(a,b,L_temp2,bisect_left(L_temp2,a+b),a+b,len(L_temp2) - bisect_left(L_temp2,a+b))
        ans += bisect_left(L_temp2,a+b)
print(ans)
### BUGGY CODE ###

n = int(input())
p = [int(i) for i in input().split()]

cnt = 1
for i in range(1,n):
	if min(p[0:i]) >= p[i]:
		cnt += 1
	#print(cnt,i)
	#print(p[0:i],p[i])
print(cnt)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

cnt = 1
m = p[0]
for i in range(1,n):
	if m > p[i-1]:
		m = p[i-1]
	if m >= p[i]:
		cnt += 1
	#print(cnt,i)
	#print(p[0:i],p[i])
print(cnt)
### BUGGY CODE ###

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

A.sort(reverse=True)
F.sort()


def judge(x):
    val = 0
    for i in range(N):
        val += max(A[i] - x // F[i], 0)
        if val > K:
            return False
    if val <= K:
        return True


ub = 10**12
lb = 0

for i in range(200):
    x = (ub+lb)/2
    if judge(x):
        ub = x
    else:
        lb = x

print(int(x))

### FIXED CODE ###

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

A.sort(reverse=True)
F.sort()


def judge(x):
    val = 0
    for i in range(N):
        val += max(A[i] - x // F[i], 0)
        if val > K:
            return False
    if val <= K:
        return True


ub = 10**12
lb = -1

while lb + 1 < ub:
    x = (ub+lb)/2
    if judge(x):
        ub = x
    else:
        lb = x

print(int(ub))
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
pnts = np.array([K] * N) - np.ones(N, int) * Q

for i in range(1, N + 1):
    if (pnts[i - 1] + A.count(i)) > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
pnts = [0] * N

for i in A:
    pnts[i - 1] += 1

for i in pnts:
    if K - Q + i > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
ans = 0

A = [["".join(sorted(input()))] for _ in range(n)]

for i in range(n-1):
    a = A[i]
    for j in range(n-i-1):
        if a == A[j+i+1]:
            ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
ans = 0

A = [["".join(sorted(input()))] for _ in range(n)]
A.sort()

k = 0

for i in range(n-1):
    if k > 1:
        k = k-1
        ans += k
    else:
        k = 0
        a = A[i]
        for j in range(n-i-1):
                if a == A[j+i+1]:
                    ans += 1
                    k += 1
                else:
                    break

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

N=int(input())

from itertools import combinations
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

d=make_divisors(N)

if math.sqrt(N)**2 ==N:
    d.append(int(math.sqrt(N)))

c= list(combinations(d,2))

# Candidate = [n for n in c if n[0]*n[1]==N]        

# # for n in c:
#     # if n[0]*n[1]==N:
#     #     Candidate.append(n)

dist=float('inf')

for i in c:
    if i[0]*i[1]==N:
        dist = min(dist,i[0]+i[1]-2)

print(dist)


### FIXED CODE ###

N=int(input())

from itertools import combinations
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

d=make_divisors(N)

if math.sqrt(N)**2 ==N:
    d.append(int(math.sqrt(N)))

dist=float('inf')
for i in d:
    j = N//i
    if i * j ==N:
        dist = min(dist,i+j-2)

print(dist)
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[None]*h
INF=10**6
from collections import deque
stack=deque()
for i in range(h):
  s=list(input())
  for j in range(len(s)):
    if s[j]=="#":
      stack.append([i,j,0])
    s[j]=INF
  grid[i]=s
      
while stack:
  v=stack.popleft()
  y=v[0]
  x=v[1]
  p=v[2]
  grid[y][x]=p
  if y-1>=0 and p+1<grid[y-1][x]:
    stack.append([y-1,x,p+1])
  if y+1<h and p+1<grid[y+1][x]:
    stack.append([y+1,x,p+1])
  if x-1>=0 and p+1<grid[y][x-1]:
    stack.append([y,x-1,p+1])
  if x+1<w and p+1<grid[y][x+1]:
    stack.append([y,x+1,p+1])
    
ans=0
for i in range(len(grid)):
  ans=max(ans,max(grid[i]))
print(ans)


### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

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

n = int(input())
A = [int(i) for i in input().split()]
k = lcm_list(A)
r = 0
for i in range(n):
    r += k//A[i]
    if r > 10**9+7:
        r %= 10**9+7
print(r)

### FIXED CODE ###

from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

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

n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
for i in ln:
    r += k//A[i]
print(r%(10**9+7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	H, W = MAP()
	N = INT()
	A = MAP()
	B = [[] for _ in range(N)]
	for i in range(N):
		B[i] = [A[i], i+1]
	B.sort(reverse=True)

	U = [[i for i in range(W, 0, -1)] for _ in range(H)]
	# print(U)
	h, w = 0, 0
	M = [[0] * W for _ in range(H)]

	painted = [0] * N
	while sum(painted) < N:
		for i, b in enumerate(B):
			cnt, num = b
			if painted[i]: continue
			# print(h, w)
			if U[h][w] >= cnt or w <= cnt - w:
				while cnt:
					M[h][w] = num
					w += 1
					cnt -= 1
					if w == W:
						h += 1
						w = 0
				painted[i] = 1

	# print(M)
	for m in M:
		print(' '.join(map(str, m)))

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
import copy
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	H, W = MAP()
	N = INT()
	A = MAP()
	# print(A)
	
	M = [[0] * W for _ in range(H)]
	# print(M)

	MOVE = [[0,1],[1,0],[0,-1],[-1,0]]

	h, w = 0, 0
	M[0][0] = 1
	A[0] -= 1
	direct = 0
	for i, a in enumerate(A):
		num = i+1
		cnt = a
		if not cnt: continue
		fin = False
		while True:
			for i, move in enumerate(MOVE):
				if i < direct:
					continue
				else:
					direct = 0
					dh, dw = move
				while h+dh < H and h+dh >= 0 and w+dw < W and w+dw >= 0 and M[h+dh][w+dw] == 0:
					h += dh
					w += dw
					M[h][w] = num
					cnt -= 1
					if cnt == 0:
						direct = MOVE.index([dh, dw])
						fin = True
						break
				if fin:	break
			if fin:	break

	for m in M:
		print(' '.join(map(str, m)))

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

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: [set(), False] for i in range(1, N+1)}
    for i, j in links:
        d[i][0].add(j)
        d[j][0].add(i)
    b = len(d[1][0])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        d[1][1] = True
        root = d[1][0]
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                d[i][1] = True
                b = len(d[i][0]) - 1
                if a < b:
                    print(0)
                    break
                children |= d[i][0]
                if b == 0:
                    continue
                ans *= perm(a, b)
            else:               
#                 for i in list(children):
#                     if d[i][1]:
#                         children.remove(i)
                if len(children) == 0:
                    print(ans % mod)
                    break
                root = children
                continue
            break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
### BUGGY CODE ###

H,W,K=map(int,input().split())
S=[[] for i in range(0,H)]
for i in range(0,H):
    S[i]=input()

ans=10**4
for i in range(0,2**(H-1)):
    segment=[]
    start=0
    end=0
    for j in range(0,H-1):
        if (i>>j) & 1==1:
            end=j
            segment.append((start,end))
            start=end+1
    segment.append((start,H-1))
    white=[0 for j in range(0,len(segment))]
    count=0
    for j in range(0,W):
        for k in range(0,len(segment)):
            start,end=segment[k]
            white[k]+=sum((int(S[r][j])&1) for r in range(start,end+1))
        if max(white)>K:
            count+=1
            for k in range(0,len(segment)):
                start,end=segment[k]
                white[k]=sum((int(S[r][j])&1) for r in range(start,end+1))
    test=count+len(segment)-1
    if test<ans:
        ans=test

print(ans)


### FIXED CODE ###

H,W,K=map(int,input().split())
S=[[] for i in range(0,H)]
for i in range(0,H):
    S[i]=input()

sumtable=[[0 for i in range(0,W)] for j in range(0,H+1)]
for i in range(1,H+1):
    for j in range(0,W):
        sumtable[i][j]=sumtable[i-1][j]+(int(S[i-1][j])&1)


ans=10**4
for i in range(0,2**(H-1)):
    segment=[]
    start=0
    end=0
    for j in range(0,H-1):
        if (i>>j) & 1==1:
            end=j
            segment.append((start,end))
            start=end+1
    segment.append((start,H-1))
    white=[0 for j in range(0,len(segment))]
    count=0
    for j in range(0,W):
        for k in range(0,len(segment)):
            start,end=segment[k]
            white[k]+=sumtable[end+1][j]-sumtable[start][j]
        if max(white)>K:
            count+=1
            for k in range(0,len(segment)):
                start,end=segment[k]
                white[k]=sumtable[end+1][j]-sumtable[start][j]
            if max(white)>K:
                break
    else:
        test=count+len(segment)-1
        if test<ans:
            ans=test

print(ans)