Harryxun/stf_run huggingface dataset:
import collections
import sys
import numpy as np

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = [int(x) for x in readline().split()]
ac = collections.Counter(A)
assert set(ac.keys()).issubset({1, 2, 3})
C1, C2, C3 = ac[1], ac[2], ac[3]
K = C1 + C2 + C3
dp = np.zeros((K + 3, C2 + C3 + 2, C3 + 1), dtype=np.float64)


def solve(c1, c2, c3):
    for i3 in range(c3 + 1):
        for i2 in range(c2 + c3 + 1):
            for i1 in range(K + 1):
                isum = i1 + i2 + i3
                i0 = N - i1 - i2 - i3
                if i0 < 0:
                    continue
                e = i0
                if i1 > 0:
                    e += i1 * (1.0 + dp[i1 - 1, i2, i3])
                if i2 > 0:
                    e += i2 * (1.0 + dp[i1 + 1, i2 - 1, i3])
                if i3 > 0:
                    e += i3 * (1.0 + dp[i1, i2 + 1, i3 - 1])
                dp[i1, i2, i3] = e / isum
    return dp[c1, c2, c3]


if __name__ == "__main__":
    print(solve(C1, C2, C3))


### FIXED CODE ###

import collections
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = [int(x) for x in readline().split()]
ac = collections.Counter(A)
assert set(ac.keys()).issubset({1, 2, 3})


def solve(c1, c2, c3):
    K = c1 + c2 + c3
    L = K + 1
    L2 = L ** 2
    dp = [0.0] * L ** 3
    for i3 in range(c3 + 1):
        for i2 in range(c2 + c3 + 1):
            for i1 in range(N - i2 - i3 + 1):
                isum = i1 + i2 + i3
                if isum == 0:
                    continue
                i0 = N - i1 - i2 - i3
                if i0 < 0:
                    continue
                e = i0
                if i1 > 0:
                    e += i1 * (1.0 + dp[(i1 - 1) * L2 + i2 * L + i3])
                if i2 > 0 and i1 <= K:
                    e += i2 * (1.0 + dp[(i1 + 1) * L2 + (i2 - 1) * L + i3])
                if i3 > 0 and i2 + 1 <= c2 + c3:
                    e += i3 * (1.0 + dp[i1 * L2 + (i2 + 1) * L + i3 - 1])
                dp[i1 * L2 + i2 * L + i3] = e / isum
    return dp[c1 * L2 + c2 * L + c3]


if __name__ == "__main__":
    print(solve(ac[1], ac[2], ac[3]))
hs = map(int, input().split())
hs.sort()
print(hs[0] * hs[1] // 2)

### FIXED CODE ###

hs = list(map(int, input().split()))
hs.sort()
print(hs[0] * hs[1] // 2)
s = input()
cnt = []
for i in range(3):
  cnt.append(s[i])
cnt.sort()
if cnt = ['a','b','c']:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = input()
cnt = []
for i in range(3):
  cnt.append(s[i])
cnt.sort()
if cnt == ['a','b','c']:
  print('Yes')
else:
  print('No')
from collections import defaultdict

S = input()
T = input()
s_li = [0] * len(S)   # 文字列Sに登場する文字の出現回数を順番に格納する
t_li = [0] * len(T)   # 文字列Tに登場する文字の出現回数を順番に格納する

# s_liを作っていく
s_cnt_dict = defaultdict(int)   # 文字ごとに出現回数をメモしていく
s_idx_dict = defaultdict(list)  # 同じ文字が出現するインデックスをメモしていく
for i in len(S):
    k = S[i]
    s_cnt_dict[k] += 1
    s_idx_dict[k].append(i)
for k in s_cnt_dict:
    for idx in s_idx_dict[k]:
        s_li[idx] = s_cnt_dict[k]

# t_liを作っていく
t_cnt_dict = defaultdict(int)   # 文字ごとに出現回数をメモしていく
t_idx_dict = defaultdict(list)  # 同じ文字が出現するインデックスをメモしていく
for i in len(T):
    k = T[i]
    t_cnt_dict[k] += 1
    t_idx_dict[k].append(i)
for k in t_cnt_dict:
    for idx in t_idx_dict[k]:
        t_li[idx] = t_cnt_dict[k]

print('Yes') if s_li == t_li else print('No')


### FIXED CODE ###

"""
S = chokudai
T = redcoder

'redcoder' には 'e' が２つあるので一度に変える必要があるが、
Sではそれに相当する場所には 'h' と 'a' の2種類の文字があるので不可能。
こういう感じで一文字ずつ見ていけばよさそう。

10 ** 5なのでstring.count()とか使っちゃうとTLEしそう。

文字の出現回数を格納するリストを作っていって、それぞれ比較すればよさそう。
上の例だと、
    s_li = [1, 1, 1, 1, 1, 1, 1, 1]
    t_li = [2, 2, 2, 1, 1, 2, 2, 2]
になり、s_liとt_liの中身が異なるのでNG。
"""
from collections import defaultdict

S = input()
T = input()
s_li = [0] * len(S)   # 文字列Sに登場する文字の出現回数を順番に格納する
t_li = [0] * len(T)   # 文字列Tに登場する文字の出現回数を順番に格納する

# s_liを作っていく
s_cnt_dict = defaultdict(int)   # 文字ごとに出現回数をメモしていく
s_idx_dict = defaultdict(list)  # 同じ文字が出現するインデックスをメモしていく
for i in range(len(S)):
    k = S[i]
    s_cnt_dict[k] += 1
    s_idx_dict[k].append(i)
for k in s_cnt_dict:
    for idx in s_idx_dict[k]:
        s_li[idx] = s_cnt_dict[k]

# t_liを作っていく
t_cnt_dict = defaultdict(int)   # 文字ごとに出現回数をメモしていく
t_idx_dict = defaultdict(list)  # 同じ文字が出現するインデックスをメモしていく
for i in range(len(T)):
    k = T[i]
    t_cnt_dict[k] += 1
    t_idx_dict[k].append(i)
for k in t_cnt_dict:
    for idx in t_idx_dict[k]:
        t_li[idx] = t_cnt_dict[k]

print('Yes') if s_li == t_li else print('No')
n,m=map(int,input().split())
if n=m:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n,m=map(int,input().split())
if n==m:
  print("Yes")
else:
  print("No")
a = int(raw_input())
b = int(raw_input())
print(str(a*b) + str((a+b)*2))

### FIXED CODE ###

data = raw_input()
dlist = data.split(' ')
a = int(dlist[0])
b = int(dlist[1])

print(str(a*b) + ' ' + str((a+b)*2))
n,k = list(map(int,imput().split()))
ans = [1] * n

for i in range(k):
  d = int(input())
  for j in list(map(int,input().split())):
    ans[j-1] = 0

print(ans.count(1))

### FIXED CODE ###

n,k = map(int,input().split())
ans = [1]*n

for i in range(k):
  d = int(input())
  for j in list(map(int,input().split())):
    ans[j-1] = 0

print(ans.count(1))
while True:
 a=input
 x,y=map(int,a.split())
 if x*y==0:break
 if x>y:print(f'{y} {x}')
 else:print(a)

### FIXED CODE ###

import sys
for s in sys.stdin:
 if'0 0\n'==s:break
 print(*sorted(map(int,s.split())))
w,h,x,y = map(int,input().split())
first = min(x*h,(w-x)*h)
second =min(y*w,(h-y)*w)
if first == second:
        print(f"{float(first)} 0")
else:
        print(f"{float(max(first,second))} 0")


### FIXED CODE ###

h,w,x,y = map(int,input().split())
ans1 = (h*w)/2
if h == 2*x and w == 2*y:
    ans2 = 1
else:
    ans2 = 0
print(ans1,ans2)
input = list(map(int, input().split()))
    print(input)

    counter5 = 0
    counter7 = 0

    for num in input:
        if num == 5:
            counter5+=1
        
        if num == 7:
            counter7+=1

    if counter5 == 2 and counter7 == 1:
        print("Yes")
    
    else:
        print("No")

### FIXED CODE ###

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

counter5 = 0
counter7 = 0

for num in l:
    if num == 5:
        counter5+=1
    
    if num == 7:
        counter7+=1

if counter5 == 2 and counter7 == 1:
    print("YES")

else:
    print("NO")
_ = input()
T = list(map(int, input().split()))
M = int(input())
for i in range(M):
  P, X = map(int, input().split())
  ans = sum(T[:P]+T[P+1])+X
  print(ans)


### FIXED CODE ###

A, op, B = input().split()
A, B = int(A), int(B)

if op == "+":
  print(A+B)
else:
  print(A-B)
from sys import argv

# Function for calc
def match(n, a, b):
    if (b - a)% 2 == 0:
        print((b-a)/2)
    else:
        mid = (n / 2)
        if (n - a) > b:
            print(b)
        else:
            print(n-a-1)

# Run match
match(int(argv[1]), int(argv[2]), int(argv[3]))


### FIXED CODE ###

# Function for calc
def match(n, a, b):
    if (b - a)% 2 == 0:
        print((b-a)/2)
    else:
        if (n - b) >= a:
            print((a)+((b-(a+1))/2))
        else:
            x=(n-b+1)
            print(x+((n-(a+x))/2))
# Run match
in_string = raw_input()
[N, A, B] = [int(v) for v in in_string.split()]
match(N, A, B)
N, K = map(int, input().split())

S = input()

if N == 1:
    print(0)
    exit()
#左端をLにする場合
now = ""
num_substr = 0
ex = ""
stack = []
for i in range(N):
    if (ex == "L" or ex == "") and S[i] == "R":
        start = i
    if ex == "R" and S[i] == "L":
        end = i-1
        stack.append((start, end))
        num_substr += 1
    ex = S[i]
#左からひっくり返す
tmp = min(K,num_substr)
num = stack[tmp-1][1]
ss = "L"*(num+1)+S[num+1:]
ll = num

for i in range(num+1,N):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            ll += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            ll += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            ll += 1


#右からひっくり返す
tmp = min(K,num_substr)
num = stack[len(stack)-tmp][0]
ss = S[:(N-1-num)]+"L"*(N-1-num)

lr = (N-1-num)

for i in range(num):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            lr += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            lr += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            lr += 1


######################################################################
#左端をRにする場合
now = ""
num_substr = 0
ex = ""
stack = []
for i in range(N):
    if (ex == "R" or ex == "") and S[i] == "L":
        start = i
    if ex == "L" and S[i] == "R":
        end = i-1
        stack.append((start, end))
        num_substr += 1
    ex = S[i]
#左からひっくり返す
tmp = min(K,num_substr)
num = stack[tmp-1][1]
ss = "R"*(num+1)+S[num+1:]
rl = num
#print(ll, tmp)
for i in range(num+1,N):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            rl += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            rl += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            rl += 1


#右からひっくり返す
tmp = min(K,num_substr)
num = stack[len(stack)-tmp][0]
ss = S[:(N-1-num)]+"R"*(N-1-num)

rr = (N-1-num)
#print(ll, tmp)
for i in range(num):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            rr += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            rr += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            rr += 1


print(max([ll,lr,rl,rr]))





### FIXED CODE ###


N, K = map(int, input().split())
S = input()

ans = 0
for x,y in zip(S, S[1:]):
    if x == y: #同じ方向を見ているとき
        ans += 1
#最大K回まで操作をして、そのたびに幸福な人が二人増える。全員同じ方向を向くとN-1
ans = N-1 if ans+2*K >= N-1 else ans+2*K
print(ans)
N,M = map(int,(input().split()))
X = list(map(int,(input().split())))
X.sort()
if M > 1:
    dist = [X[i+1]-X[i] for i in range(M - 1)]
    dist.sort(reverse = True)
    for i in range(N - 1):
        del dist[0]
    print(sum(dist))
else:
 print(0)

### FIXED CODE ###

N,M = map(int,(input().split()))
X = list(map(int,(input().split())))
X.sort()
if M > N:
    dist = [X[i+1]-X[i] for i in range(M - 1)]
    dist.sort(reverse = True)
    for i in range(N - 1):
        del dist[0]
    print(sum(dist))
else:
 print(0)
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            while self.parent[x] >= 0:
                self.parent[x] = self.parent[self.parent[x]]
                x = self.parent[x]
#        self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


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

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

ans = [0]*(m+1)
a = n*(n-1)//2
ans[0] = a

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

for i in range(m):
    print(ans[m-i-1])
    
    
    
    
    
    





### FIXED CODE ###

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]


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

A=[[int(i)-1 for i in input().split()] for _ in range(m)]

ans = [0]*(m+1)
a = n*(n-1)//2
ans[0] = a

uf = UnionFind(n)
for i in range(m):
    j = m-i-1
    v1 = A[j][0]
    v2 = A[j][1]
#    print(v1,v2)
    if not uf.issame(v1,v2):
#        print(uf.parent)
        a -= uf.size(v1) * uf.size(v2)
        uf.merge(v1,v2)

    ans[i+1]=a

for i in range(m):
    print(ans[m-i-1])
n,y = map(int,input().split()) #n枚,y円
a = -1
b = -1
c = -1


for i in range(n+1):
    for j in range(n+1):
        k = n-i-j
        if i*10000+j*5000+k*1000 == y and z >= 0 :
            a = i
            b = j
            c = k
print(a,b,c)
            

### FIXED CODE ###

n,y = map(int,input().split()) #n枚,y円
a = -1
b = -1
c = -1
for i in range(n+1):
    for j in range(n+1):
        k = n-i-j
        if i*10000+j*5000+k*1000 == y and k >= 0 :
            a = i
            b = j
            c = k
            break

print(a,b,c)
a, b = int(input().split)
print(a*b, (a+b)*2)


### FIXED CODE ###

a, b = map(int, input().split())
print(a * b, (a + b) * 2)
import collections
n,c  = map(int,input().split())                     
channels = [list(map(int,input().split())) for i in range(n)]
print(channels)
channel_set = [list(range(i[0],i[1]+1)) for i in channels]
channels = []                                                
for ch in channel_set:
    channels.extend(ch)                                   
print(channels)                                  
#map(int,input().split())                                           c = collections.Counter(channels)
print(c.most_common()[0][1])

### FIXED CODE ###

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

def inc(n):
  return n+1
def dec(n):
  return n-1

history = {}
for i in range(N):
  s,t,c = map(int,input().split())
  s *= 2
  t *= 2
  #print(history)
  if (t-1) in history and c in history[t-1]:
    history[t-1].pop(c)
  else:
    if t in history:
      history[t][c] = dec
    else:history[t] = {c:dec}
  if (s) in history and c in history[s]:
    history[s].pop(c)
  else:
    #history[s-0.5][c] = inc
    if s-1 in history:
      history[s-1][c] = inc
    else:
      history[s-1] = {c:inc}
maximum = 0
counter = 0
for i in range(100000*2):
  if i in history:
    for func in history[i].values():
      counter = func(counter)
    if counter > maximum:
      maximum = counter
#print(history)
print(maximum)
n = int(input())

for _ in range(n):
  m, f, r = map(int, input().split())
  s = m+f

if s >= 80:
    print("A")
elif s >= 65 && s < 80:
    print("B")
elif s >= 50 && s < 65 || f >= 50:
    print("C")
elif s >= 30 && s < 50:
    print("D")
else:
    print("F")


if m == f == r== -1:
    print("F")



### FIXED CODE ###

while True:
    m, f, r = map(int, input().split())
    if m == f == r== -1:
        break
    s = m + f
    if m == -1 or f == -1:
        print("F")
    elif s >= 80:
        print("A")
    elif s >= 65:
        print("B")
    elif s >= 50:
        print("C")
    elif s >= 30:
        if r >= 50:
            print("C")
        else:
            print("D")
    else:
        print("F")
import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n,k=map(int,input().split())
A=list(map(int,input().split()))
#n,k=5,3
#A=[-30,-10,10,20,40]
ans=inf
for i in range(n-k+1):
    ans=min(ans, abs(A[i])+abs(A[i]-A[i+k-1]), abs(A[i+k-1])+abs(A[i+k-1]-A[i]) )
print(ans)

### FIXED CODE ###

import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n,m=map(int,input().split())
query=[]
for i in range(m):
    a,b=map(int,input().split())
    query.append([a,b])
query.sort(key=lambda x:x[1])

tekyo=-1
kazu=0
for i in range(m):
    a,b=query[i][0],query[i][1]
    if tekyo<a: #キレてない
        tekyo=b-1
        kazu+=1
print(kazu)
よこ，たて，_ = map(int,input().split())
こたえ=よこ*たて//2
print(こたえ)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

AB, BC, CA = [int(x.strip("|")) for x in input().split()]
print(int(AB*BC/2))
N = int(input())

c=False
for (i in range(25)):
        for(j in range(7)):
            if(i*4+7*j==N):
                c=True
                break
if(c):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
K=4
D=7
c=False
for i in range(25):
        for j in range(7):
            if(i*K+D*j==N):
                c=True
                break
if(c):
    print("Yes")
else:
    print("No")
n, a, b = map(int, input().split())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
l = []
for r in range(1, n+1):
    if r != a and r != b:
        l.append(cmb(n,r,mod))

print(sum(l))

### FIXED CODE ###

def cmb(n, r, p):
    r = min(r, n - r)
    upper = 1
    for i in range(n, n - r, -1):
        upper = (upper * i) % p

    lower = 1
    for i in range(1, r + 1):
        lower = (lower * i) % p

    # フェルマーの小定理よりp素数ならupper**(p-2)は逆元
    return (upper * pow(lower, p - 2, p)) % p

mod = pow(10, 9) + 7
n, a, b = map(int, input().split())
ans = (pow(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod))%mod
print(ans)
H, W, K = map(int,input().split())
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1

ck = [0]*9
for i in range(1,9):
  for j in range(2**i):
    for k in range(i-1):
      if k&(k+1)==True:
        continue
    else:
      ck[i] += 1

mod = 10**9+7
for i in range(1,H+1):
  for j in range(W):
    if j == 0:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j+1]*ck[W-3]
    elif j == W-1:
      dp[i][j] = dp[i-1][j]*ck[W-2]+dp[i-1][j-1]*ck[W-3] 
    else:
      dp[i][j] = dp[i-1][j+1]*(ck[j-2]+ck[W-2-j])+dp[i-1][j]*(ck[j-1]+ck[W-1-j])+dp[i-1][j-1]*(ck[j]+ck[W-j])
      
print(dp[H][K-1])
    
    
  

### FIXED CODE ###

H, W, K = map(int,input().split())
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1

ck = [0]*9
ck[0] = 1
for i in range(1,9):
  for j in range(2**(i-1)):
    for k in range(i-1):
      if (j>>k)&(j>>(k+1))==True:
        break
    else:
      ck[i] += 1

mod = 10**9+7
for i in range(1,H+1):
  for j in range(W):
    if (j == 0)&(j == W-1):
      dp[i][j] = dp[i-1][j]*(ck[j]*ck[W-1-j])
    elif j == 0:
      dp[i][j] = dp[i-1][j+1]*(ck[j]*ck[W-j-2])+dp[i-1][j]*(ck[j]*ck[W-1-j])
    elif j == W-1:
      dp[i][j] = dp[i-1][j]*(ck[j]*ck[W-1-j])+dp[i-1][j-1]*(ck[j-1]*ck[W-j-1])
    else:
      dp[i][j] = dp[i-1][j+1]*(ck[j]*ck[W-j-2])+dp[i-1][j]*(ck[j]*ck[W-1-j])+dp[i-1][j-1]*(ck[j-1]*ck[W-j-1])

print(dp[H][K-1]%mod)
n = int(input())
s = input
count = 0
for i in range(n-1):
  if s[i]  != s[i+1];
    count = count + 1
print(count)

### FIXED CODE ###

n = int(input())
s = input()
count = 1
for i in range(n-1):
  if s[i+1]  != s[i]:
    count = count + 1
print(count)
a=list(map(int,input().split(" ")))
n=a[0]
m=a[1]
touhyou=list(map(int,input().split(" ")))
s=flaot(sum(touhyou)/4/m)
list=[]
for i in touhyou:
  if i>=s:
    list.append(i)
if len(list)>=m:
  print("Yes")
else:
  print("No" )

### FIXED CODE ###

a=list(input().split(" "))
print(a[2]+" "+a[0]+" "+a[1] )
N = input()
mod = int(N[0] + N[1] + N[2])

print("Yes" if int(N) % mod == 0 else "No")

### FIXED CODE ###

N = input()
sum = 0

for i in range(len(N)):
    sum += int(N[i])
print("Yes" if int(N) % sum == 0 else "No")
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,K = MI()
S = LI2()

A = []
a = 1
for i in range(1,N):
    if S[i-1] == S[i]:
        a += 1
    else:
        A.append(a)
        a = 1
A.append(a)

l = len(A)
if l <= 2*K-1:
    print(N)
    exit()

if S[0] == 1:
    A = [1]+A
if S[-1] == 1:
    A = A+[1]

A = [0]+A
l = len(A)

from itertools import accumulate

A = list(accumulate(A))
ans = 0
for i in range(l//2-K+1):
    if i == 0:
        ans = max(ans,A[2*(K+i)]-A[2*i])
    elif i == l//2-K:
        ans = max(ans,A[2*(K+i)-1]-A[2*i-1])
    else:
        ans = max(ans,A[2*(K+i)]-A[2*i-1])

print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


A = LS2()
N = len(A)

from collections import defaultdict

d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1


ans = 0
for key in d.keys():
    ans += d[key]*(N-d[key])

ans //= 2
ans += 1
print(ans)
import sys

s = sys.stdin.read().strip()
words = ["dream", "dreamer", "erase", "eraser"]

def dfs(i):
  for w in words:
    if s.startswith(w, i):
      n = i + len(w)
      if n == len(s):
        return True
      if dfs(n):
        return True
  return False

print("YES" if dfs(0) else "NO")


### FIXED CODE ###

import sys

s = sys.stdin.read().strip()
words = ["dream", "dreamer", "erase", "eraser"]

stack = [0]
match = False
while not match and stack:
  i = stack.pop()
  for w in words:
    if s.startswith(w, i):
      n = i + len(w)
      if n == len(s):
        match = True
        break
      stack.append(n)
print("YES" if match else "NO")