Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10000)

N,M, K = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]
CD = [list(map(int,input().split())) for i in range(K)]


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x]=y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(min(a-1,b-1),max(a-1,b-1),li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1)+1)]
for i in range(N):
    m = root(i,li1)
    mm[m] += 1

print(li1,file=sys.stderr)
print(mm,file=sys.stderr)
ans = [mm[li1[i]]-1 for i in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)





### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N,M, K = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]
CD = [list(map(int,input().split())) for i in range(K)]


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x]=y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    # print(str(i)+" ",end="")
    union(min(a-1,b-1),max(a-1,b-1),li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1)+1)]
for i in range(N):
    m = root(i,li1)
    mm[m] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]]-1 for i in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)
while True:
    [n,m,a]=input().split()
    if [n,m,a]==["0","0","0"]: break
    [n,m,a]=[int(n),int(m),int(a)]
    yokobo={}
    for k in range(m):
        [h,p,q]=input().sprit()
        yokobo[h,p]=[int(q)]
        yokobo[h,q]=[int(p)]
    move=1000
    while move>0:
        a=yokobo[move,a]
        move=move-1

### FIXED CODE ###

while True:
    [n,m,a]=input().split()
    if [n,m,a]==["0","0","0"]: break
    [n,m]=[int(n),int(m)]
    yokobo={}
    for k in range(m):
        [h,p,q]=input().split()
        yokobo[h,p]=q
        yokobo[h,q]=p
    high=1000
    while high>0:
        if (str(high),a) in yokobo:
            a=yokobo[str(high),a]
        high-=1
    print(a)
N=int(input())
List=list(map(int,input().split()))
c=0
for i in range(N-1):
  for j in range(i+1:N):
    c=c+(List[i]*List[j])
print(c)

### FIXED CODE ###

a,b=map(int,input().split())
c=a-2*b
if c<=0:
    print(0)
else:
    print(c)
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

n = int(input())
print(lcm(2,n))

### FIXED CODE ###

import fractions

n = int(input())
print(n * 2 // fractions.gcd(2, n))
a = input()
b = input()
print(int(a)*int(b),2*(int(a)+int(b))

### FIXED CODE ###

a,b = map(int,input().split())
print(a*b,2*(a+b))
import sys
n = int(input())
a=[]
a=list(map(int, input().split()))
m=[0]*n
for i in list(reversed(range(a[0])):
  mn=0
  for j in range(n-1):
    if j==0:
      m[n-1]=i*2
      m[j]=(a[j]-m[n-1]/2)*2
    else:
      m[j]=(a[j]-m[j-1]/2)*2

  if m[n-2]/2+m[n-1]/2 ==a[n-1]:
    print(int(m[n-1]),sep=" ",end=" ")
    for i in range(n-1):
      print(int(m[i]),sep=" ",end=" ")


    sys.exit()
  

### FIXED CODE ###

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

m=[0]*n

for i in range(n):
  if i%2 == 0:
    m[0]+=a[i]
  else:
    m[0]-=a[i]
for i in range(1,n):
  m[i] =(a[i-1]-m[i-1]/2)*2
  
for i in range(n):
  print(int(m[i]),end=" ")
N=int(input())
for i in range(1,3501):
  for j in range(1,3501):
    w=(N*i*j)/(4*i*j-N*i-N*j)
    if w>0 and w.is_integer():
      print(i,j,int(w))
      exit()

### FIXED CODE ###

N=int(input())
if N%2==0:
  print(N//2,N,N)
else:
  for i in range(1,3501):
    for j in range(1,3501):
      if 4*i*j-N*i-N*j!=0:
        w=(N*i*j)/(4*i*j-N*i-N*j)
        if w>0 and w.is_integer():
          print(i,j,int(w))
          exit()
n,m = map(int,input().split())
a = list(input())

a[m] = a[m].replace("A","a").replace("B","b").replace("C","c")
print("".join(a))


### FIXED CODE ###

import sys,collections as cl,bisect as bs
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

n,m = m()
a = list(input())

if a[m-1] == "A":
	a[m-1] = "a"
elif a[m-1] == "B":
	a[m-1] = "b"
else:
	a[m-1] = "c"
print("".join(a))
while True:
  H, W = map(int, raw_input().split())
  if H == 0 and W == 0:
    break
  for i in range(H):
    width = "#"
    if i == 0 or i == H - 1:
      for j in range(1,W):
        width += "#"
      print width
    else:
       for j in range(1,W-1):
        width += "."
      width += "#"
      print width
  print ""

### FIXED CODE ###

while True:
  H, W = map(int, raw_input().split())
  if H == 0 and W == 0:
    break
  print "#"*W
  for i in range(H-2):
    if W > 2:
      print "#" + "."*(W-2) + "#"
    else:
      print "#"*W 
  print "#"*W
  print ""
a = input()
print(700 + int(input()).count('o'))

### FIXED CODE ###

print(700 + int(input().count('o')) * 100)
import numpy as np

def main():
  N = int(input())
  A = list(map(int,input().split()))
  A.sort()
  d = np.zeros(A[-1]+1, dtype=np.unit64)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
      if a != a1:
        d[a::a] += 1
      else:
        d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
print(main())

### FIXED CODE ###

import numpy as np

def main():
  N = int(input())
  A = list(map(int,input().split()))
  A.sort()
  d = np.zeros(A[-1]+1, dtype=np.uint64)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
      d[a::a] += 1
    else:
      d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
main()
input();l=input().split();x=1
for j in sorted(l):x*=int(j)
  if x>1e18:x=-1;break
print(x)

### FIXED CODE ###

i = input
i()
x = 1
l = i().split()
if '0' in l:
    print(0)
    quit()
for j in l:
    x *= int(j)
    if x > 1e18:
        print(-1)
        quit()
print(x)
import collections as c
import sys
s = input()
l = len(s)

if l == 1:
	print("NO")
else:
	S = c.Counter(list(map(str,s)))

	if len(S.keys()) <= 2:
		if l == 2:
			print("YES")
		else:
			print("NO")
		sys.eixt()

	cnt = set(list(S.values()))

	if len(cnt) == 3:
		print("NO")
	elif len(cnt) == 2:
		a,b = cnt
		if abs(a-b) <= 1:
			print("YES")
		else:
			print("NO")
	else:
		print("YES")

### FIXED CODE ###

import collections as c
import sys
s = input()
l = len(s)

if l == 1:
	print("YES")
else:
	S = c.Counter(list(map(str,s)))
	if len(S.keys()) == 1:
		print("NO")
		sys.exit()
	elif len(S.keys()) == 2:
		if l == 2:
			print("YES")
		else:
			print("NO")
		sys.exit()

	cnt = set(list(S.values()))

	if len(cnt) == 3:
		print("NO")
	elif len(cnt) == 2:
		a,b = cnt
		if abs(a-b) <= 1:
			print("YES")
		else:
			print("NO")
	else:
		print("YES")
n, k = map(int, input().split())

t = []
d = k
while(True):
  d = d / 2
  t.append(d)
  if d <= 1:
    break
# print(t)

t2 = []
for i in range(1, 1+n):
  for j in range(len(t)):
    if i >= t[j]:
      t2.append(j+1)
      break
# print(t2)

t3 = [0.5]
for i in range(1, len(t2)+2):
  t3.append(t3[i-1]*0.5)
# print(t3)

r = 0
for t in t2:
  r += t3[t-1]
print(r/n)


### FIXED CODE ###

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

r = 0
for i in range(1, 1+n):
  t = i
  p = 1.0
  while(True):
    if t >= k:
      r += p
      break
    t *= 2
    p *= 0.5
print(r/n)
H, W = map(int, input().split())
a = [""] * H
for i in range(H):
    a[i] = input()
row = [False] * H
col = [False] * W
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            row[i] = True
            col[i] = True
for i in range(H):
    if row[i]:
        for j in range(W):
            if col[j]:
                print(a[i][j], end = "")
        print()

### FIXED CODE ###

h, w = map(int, input().split())
a = [''] * h
for i in range(h):
	a[i] = input()
 
row = [False] * h
col = [False] * w
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			row[i] = True
			col[j] = True
 
for i in range(h):
	if row[i]:
		for j in range(w):
			if col[j]:
				print(a[i][j], end = '')
		print()
while True:
    m, f, r = [int(i) for i in input().split()]

    if m == f == r == -1:
        break

    total = m + f
    if m == -1 or f == -1 or total< 30:
        print('F')

    elif total < 50 anfd r < 50:
        print('D')

    elif total < 65:
        print('C')
        
    elif total < 80:
        print('B')
        
    else:
        print('A')

### FIXED CODE ###



while True:
   m, f, r = [int(i) for i in input().split()]
  
   if m == f == r == -1:
      break
   total = m + f
   if m == -1 or f == -1 or total < 30:
      print("F")
    
   elif total < 50 and r < 50:
      print("D")
 
   elif r >= 50 or total < 65:
      print("C")
    
   elif total < 80:
      print("B")
 
   else:
      print("A")
N = int(input())
P = list(map(int, input().split()))

ans = 0
for i in range(N):
    if P[i] == i+1:
        tmp = P[i]
        P[i] = P[i+1]
        P[i+1] = tmp
        ans += 1


for i in range(N):
    if P[i] == i+1:
        ans += 1

print(ans)

### FIXED CODE ###

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

ans = 0
bin_box = []

for i in range(len(p)):
    if i+1 == p[i]:
        bin_box.append(1)
    else:
        bin_box.append(0)

bin_box.append(0)

i = 0
while i < len(bin_box):
    if bin_box[i] == 1:
        ans += 1
        if bin_box[i+1] == 1:
            i += 1
    
    i += 1
    
print(ans)
import math

A, B, K_ban = map(int, input().split())

gc = math.gcd(A, B)
ctr = 1

while (gc > 0):

    if (A % gc == 0 and B % gc == 0):
        
        if (ctr == K_ban):
            print(gc)
            break
        else:
            ctr += 1
    
    gc -= 1

### FIXED CODE ###

import fractions

A, B, K_ban = map(int, input().split())

gc = fractions.gcd(A, B)
ctr = 1

while (gc > 0):

    if (A % gc == 0 and B % gc == 0):
        
        if (ctr == K_ban):
            print(gc)
            break
        else:
            ctr += 1
    
    gc -= 1
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
for i in range(M):
    A[i] , B[i] = map(int, input().split())

uf = UnionFind(N)
for i in range(M):
    uf.union(A[i], B[i])
print(uf.group_count()-1)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
for i in range(M):
    A[i] , B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1






uf = UnionFind(N)
for i in range(M):
    uf.union(A[i], B[i])
print(uf.group_count()-1)
a , b = map(int,input().split())
 
 
list = []
papa = ""
 
for i in range(b):
  list.append(input())
  
list.sort()
for x in list:
  papa += x
print(papa)

### FIXED CODE ###

a , b = map(int,input().split())
c_list = sorted([input() for i in range(a)])
print("".join(c_list))
n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = n//mod
  x = n//mod
  loop = 0
  while(x>0 and loop<10**7):
    loop += 1
    mod *= 5
    x = n//mod
    ans+=x
print(ans)

### FIXED CODE ###

n = int(input())

if n %2 ==1:
  print(0)
else:
  mod = 10
  ans = 0
  x = 0
  while True:
    x = n//mod
    if x==0: break
    ans+=x
    mod *= 5
  print(ans)
n = int(input())
a = list(map(int,input().split()))
al = [0] * n
for i in range(n):
  al[i] = abs(a[i+1] - a[i])
s = sum(al)
for i in range(n):
  print(s-al[i-1]-al[i]+abs(a[i+1]-a[i-1]))

### FIXED CODE ###

n = int(input())
ai = list(map(int,input().split()))
a = [0]
for i in ai:
  a.append(i)
al = [0] * (n+1)
for i in range(n+1):
  al[i] = abs(a[(i+1)%(n+1)] - a[i])
s = sum(al)
for i in range(1,n+1):
  print(s-al[i-1]-al[i]+abs(a[(i+1)%(n+1)]-a[i-1]))
from numba import jit
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

@jit
def DFS(add,next):
    global cnt
    x,y=add
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        X,Y=x+i,y+j
        if 0<=X<h and 0<=Y<w:
            if S[X][Y]==next and color[X][Y]=="white":
                color[X][Y]="black"
                DFS([X,Y],"." if next=="#" else "#")
                if next==".":cnt +=1


h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]
cnt=0

for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            color=[["white" for _ in range(w)] for _ in range(h)]
            color[i][j]="black"
            DFS([i,j],".")

print(cnt)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline


def DFS(add,next,cnt):
    x,y=add
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        X,Y=x+i,y+j
        if 0<=X<h and 0<=Y<w:
            if S[X][Y]==next and color[X][Y]=="white":
                color[X][Y]=str(cnt)
                DFS([X,Y],"." if next=="#" else "#",cnt)


h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]
cnt=0

color=[["white" for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        if S[i][j]=="#" and color[i][j]=="white":
            cnt +=1
            DFS([i,j],".",cnt)

dictionary={str(i+1):[0,0] for i in range(cnt)}
for i in range(h):
    for j in range(w):
        if color[i][j]!="white":
            if S[i][j]==".":dictionary[color[i][j]][0] +=1
            else:dictionary[color[i][j]][1] +=1

ans=0
for v,m in dictionary.values():
    ans +=v*m
print(ans)
while 1:
    input = raw_input()
    output = ""

    for i in input:
        if i.islower():
            output += i.upper()
        elif i.isupper():
            output += i.lower()
    
    print(output)

### FIXED CODE ###

print raw_input().swapcase()
A = [[1,3,5,7,8,10,12],[4,6,9,11],[2]]
x,y = map(int, input().split())
flg = 0
for a in A:
    if x in a and y in a:
        flg = 1

if flg = 1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

A = [[1,3,5,7,8,10,12],[4,6,9,11],[2]]
x,y = map(int, input().split())
flg = 0
for a in A:
    if x in a and y in a:
        flg = 1

if flg == 1:
    print("Yes")
else:
    print("No")
data = input(split())
A = data[0]
B = data[1]

if A < 10 and B < 10:
  print(A * B)
else:
  print('-1')

### FIXED CODE ###

data = input().split()
A = int(data[0])
B = int(data[1])

if A < 10 and B < 10:
  print(str(A * B))
else:
  print('-1')
num = input().split(' ')
x = num[0]
y = num[1]

if x > y:
  tmp = x
  x = y
  y = tmp

elif x = y = 0:
  exit()

else:
  break

print(x + ' ' +y)


### FIXED CODE ###

while(True):
    x, y = map(int, input().split())
    if(x == y == 0):
        break
    if(x <= y):
        print("%d %d" % (x, y))
    else:
        print("%d %d" % (y, x))
n = int(input())
a = list(map(int,input().split()))
ma = []
pa = []
l =[]
t = 0
for i in a:
  if i < 0:
    ma.append(i)
    l.append(i*-1)
  elif i> 0:
    pa.append(i)
    l.append(i)
  else:
    t = 1
s = sum(l)
print(s  if t == 1 or len(b)%2==0 else s - 2*min(l))


### FIXED CODE ###


n = int(input())
a = list(map(int,input().split()))
ma = []
pa = []
l =[]
t = 0
k  = 0
for i in a:
  if i < 0:
    ma.append(i)
    l.append(i*-1)
    k+=1
  elif i> 0:
    pa.append(i)
    l.append(i)
  else:
    t = 1
s = sum(l)
print(s  if t == 1 or k%2==0 else s - 2*min(l))
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N,M=map(int,input().split())
    A=[list(map(int,input().split())) for i in range(N)]
    B=[list(map(int,input().split())) for i in range(M)]

    for i in A:
        valmin=10**5
        cnt=0
        for j in B:
            if abs(i[0]-j[0])+abs(i[1]-j[1])<valmin:
                valmin=abs(i[0]-j[0])+abs(i[1]-j[1])
                ans=cnt+1
            cnt+=1
        print(ans)





resolve()

### FIXED CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N,M=map(int,input().split())
    A=[list(map(int,input().split())) for i in range(N)]
    B=[list(map(int,input().split())) for i in range(M)]

    for i in A:
        valmin=10**5
        cnt=0
        l=[]
        for j in B:
            l.append(abs(i[0]-j[0])+abs(i[1]-j[1]))
        print(l.index(min(l))+1)





resolve()
"""
15,8,5の場合：
何回右に移動するか、何回左に移動するか。
dp[i][j] => i回目下降が終わった時点で、j列目にいる場合の数
memo[j] => 特定の高さを見たときに、j列目とj+1列目の間に横棒があるような横棒配置パターン数
memo2[j] => j列目の左右に横棒がないような場合の数
"""
mod = 10**9 +7
H,W,K = map(int,input().split())
memo = [0]*(W-1)
memo2 = [0]*(W-1)
cnt = 0
for i in range(2**(W-1)):
    binI = format(i,"0"+str(W-1)+"b")
    #パターンの有効性をチェックする
    for j in range(W-2):
        if binI[j] == "1" and binI[j+1] == "1":
            break
    else:
        cnt += 1
        for j in range(W-1):
            if binI[j] == "1":
                memo[j] += 1
        for j in range(1,W-1):
            if binI[j-1]=="0" and binI[j] =="0":
                memo2[j] += 1
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        #右の列に移動する
        if j != W-1:
            dp[i+1][j+1] += memo[j]*dp[i][j]%mod
            dp[i+1][j+1] %= mod
        #左の列に移動する
        if j != 0:
            dp[i+1][j-1] += memo[j-1]*dp[i][j]%mod
            dp[i+1][j-1] %= mod
        #真下に移動する
        if j == 0:
            dp[i+1][j] += (cnt-memo[j])*dp[i][j]%mod
        elif j == W-1:
            dp[i+1][j] += (cnt-memo[j-1])*dp[i][j]%mod
        else:
            dp[i+1][j] += memo2[j]*dp[i][j]%mod
        dp[i+1][j]%=mod

print(dp[-1][K-1])

### FIXED CODE ###

"""
15,8,5の場合：
何回右に移動するか、何回左に移動するか。
dp[i][j] => i回目下降が終わった時点で、j列目にいる場合の数
memo[j] => 特定の高さを見たときに、j列目とj+1列目の間に横棒があるような横棒配置パターン数
memo2[j] => j列目の左右に横棒がないような場合の数
"""
mod = 10**9 +7
H,W,K = map(int,input().split())
if W == 1:
    print(1)
    exit()
memo = [0]*(W-1)
memo2 = [0]*(W-1)
cnt = 0
for i in range(2**(W-1)):
    binI = format(i,"0"+str(W-1)+"b")
    #パターンの有効性をチェックする
    for j in range(W-2):
        if binI[j] == "1" and binI[j+1] == "1":
            break
    else:
        cnt += 1
        for j in range(W-1):
            if binI[j] == "1":
                memo[j] += 1
        for j in range(1,W-1):
            if binI[j-1]=="0" and binI[j] =="0":
                memo2[j] += 1
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        #右の列に移動する
        if j != W-1:
            dp[i+1][j+1] += memo[j]*dp[i][j]%mod
            dp[i+1][j+1] %= mod
        #左の列に移動する
        if j != 0:
            dp[i+1][j-1] += memo[j-1]*dp[i][j]%mod
            dp[i+1][j-1] %= mod
        #真下に移動する
        if j == 0:
            dp[i+1][j] += (cnt-memo[j])*dp[i][j]%mod
        elif j == W-1:
            dp[i+1][j] += (cnt-memo[j-1])*dp[i][j]%mod
        else:
            dp[i+1][j] += memo2[j]*dp[i][j]%mod
        dp[i+1][j]%=mod

print(dp[-1][K-1])
while True:
    h,w=map(int,input().split())
    if h+w==0:break
    for x in range(1,h+1):
    print("#"*w)

### FIXED CODE ###

while True:
    h,w=map(int, input().split())
    if h==w== 0:break
    print(('#' * w + '\n') * h)