Harryxun/stf_run huggingface dataset:
#D問題
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

N, K = map(int, input().split())
red = N - K
for i in range(K):
    if i+1 ==1:
        ans = (red+1)
        print(ans)
    else:
        if i + 1 < K:
            divide_line = combinations_count(red+1, i+1)
            case =combinations_count(K-1,i) * divide_line
            ans = case%(10**9+7)
            print(ans)
        else:
            ans = combinations_count(red+1,K)%(10**9 + 7)
            print(ans)
    

### FIXED CODE ###

#D問題
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

N, K = map(int, input().split())
red = N - K
for i in range(1,K+1):
        if N-K+1 < i:
            print(0)
        else:
            divide_line = combinations_count(red+1, i)
            case =combinations_count(K-1,i-1) * divide_line
            ans = case%(10**9+7)
            print(ans)
a=int(input())
b=int(input())
print((a*b)+' '+(2a+2b))


### FIXED CODE ###

a, b = map(int, input().split())
print(str(a * b) + " " + str(2 * a + 2 * b))
N = list(map(int,input().split()))
math = N[0] * N[1]
 if math % 2 == 1
  return Odd
 else 
  return Even

### FIXED CODE ###

N = list(map(int,input().split()))
math = N[0] * N[1]
if math % 2 == 1:
  print("Odd")
else:
  print("Even")
n, m, x = map(int, input().split())

a = [[0] * m for j in range(n)]
c = [0] * n

ans = 10**10

for i in range(n):
    arr = list(map(int, input().split()))
    c[i] = arr[0]
    a[i] = arr[1:]

# bit全探索
import itertools
for bit in itertools.product([0,1], repeat=10):
    arr = [0] * m
    cost = 0
    for i in range(n):
        if bit[i] == 1:
            for k in range(len(a[i])):
                arr[k] += a[i][k]
            cost += c[i]

    NG = False
    for i in range(len(arr)):
        if arr[i] < x:
            NG = True
            
    if NG:
        pass
    else:
        ans = min(ans,cost)

if ans != 10**10:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

n, m, x = map(int, input().split())

a = [[0] * m for j in range(n)]
c = [0] * n

ans = 10**10

for i in range(n):
    arr = list(map(int, input().split()))
    c[i] = arr[0]
    a[i] = arr[1:]

# bit全探索
import itertools
for bit in itertools.product([0,1], repeat=n):
    arr = [0] * m
    cost = 0
    for i in range(n):
        if bit[i] == 1:
            for k in range(len(a[i])):
                arr[k] += a[i][k]
            cost += c[i]

    NG = False
    for i in range(len(arr)):
        if arr[i] < x:
            NG = True
            
    if NG:
        pass
    else:
        ans = min(ans,cost)

if ans != 10**10:
    print(ans)
else:
    print(-1)
# coding: utf-8
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

@lru_cache(maxsize = None)
def f(v):
    if len(arc[v]) == 0:
        return(0)
    return(max(f(nv) for nv in arc[v]) + 1)

n, m = map(int, input().split()) # 2 <= n <= 10^5, 1 <= m <= 10^5
arc = [[] for _ in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    arc[x].append(y)
print(max(f(v + 1) for v in range(n)))


### FIXED CODE ###

# coding: utf-8
from functools import lru_cache

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

@lru_cache(maxsize = None)
def f(v):
    if not arc[v]:
        return(0)
    return(max(f(nv) for nv in arc[v]) + 1)

n, m = map(int, input().split()) # 2 <= n <= 10^5, 1 <= m <= 10^5
arc = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    arc[x - 1].append(y - 1)
print(max(f(v) for v in range(n)))
import numpy as np
n = int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
ary = np.array(ary,dtype=int)
dp = np.zeros((n,3),dtype=int)
dp[0] = ary[0]
for i in range(1,n):
    for j in range(3):
        for k in range(3):
            if j == k:continue
            if dp[i][j] < dp[i-1][k]+ary[i][j]:
                dp[i][j] = dp[i-1][k] + ary[i][j]
print(max(dp[n-1]))

### FIXED CODE ###

nums = int(input())
ary = [0 for i in range(nums)]
for i in range(nums):
    ary[i] = list(map(int,input().split()))

dp = [0 for i in range(nums+1)]
for i in range(len(dp)):
    dp[i] = [0,0,0]

for i in range(nums):
    for x in range(3):
        for y in range(3):
            if x == y: continue
            check = dp[i][x] + ary[i][y]
            if check >= dp[i+1][y]:
                dp[i+1][y] = check

result= 0
for i in range(3):
    if result < dp[nums][i]:
        result = dp[nums][i]
print(result)
def main():
    n = int(input())
    s = [int(input()) for _ in range(n)]
    s.sort()
    s_sum = sum(s)
    if s_sum % 10 != 0:
        print(s_sum)
        exit()
    for es in s:
        s_sum -= es
        if s_sum % 10 != 0:
            print(s_sum)
            exit()
	else:
      print(0)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    s = [int(input()) for _ in range(n)]
    s_sum = sum(s)
    s = [i for i in s if i % 10 != 0]
    s.sort()
    if s_sum % 10 != 0:
        print(s_sum)
        exit()
    for es in s:
        if (s_sum - es) % 10 != 0:
            print(s_sum - es)
            exit()
    else:
        print(0)

if __name__ == '__main__':
    main()
r = input()
ans = int(r)**2
return ans

### FIXED CODE ###

r = int(input())
print(r**2)
N,K = list(map(int,input().split()))
edges = [[] for _ in range(N+1)]

import operator as op
from functools import reduce

MOD = 1000000007

for _ in range(N-1):
    (e1, e2) = tuple(map(int, input().split()))
    edges[e1].append(e2)
    edges[e2].append(e1)

children = [[] for _ in range(N+1)]
seen = set()
stack = []

stack.append(1)
seen.add(1)

while stack:
    node = stack[-1]
    stack.pop()
    for edge in edges[node]:
        if edge not in seen:
            seen.add(edge)
            children[node].append(edge)
            stack.append(edge)

def solve(node, siblings, depth):
    num_children = len(children[node])

    has_grandparent = depth >= 2
    has_parent = depth >= 1

    ans = max(0, K-(siblings)-int(has_parent)-int(has_grandparent))
    if ans == 0:
        return 0

    child_siblings = 0
    for child in children[node]:
        ans *=  solve(child, child_siblings, depth+1)
        ans %= MOD
        child_siblings += 1
    return ans

if N == 1:
    print(K)
elif N == 2:
    if K >= 2:
        print(K*(K-1)//2)
    else:
        print(0)
else:
    print(solve(1, 0, 0) % MOD)



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

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

MOD = 1000000007

for _ in range(N-1):
    (e1, e2) = tuple(map(int, input().split()))
    edges[e1].append(e2)
    edges[e2].append(e1)

children = [[] for _ in range(N+1)]
seen = set()
stack = []

stack.append(1)
seen.add(1)

while stack:
    node = stack[-1]
    stack.pop()
    for edge in edges[node]:
        if edge not in seen:
            seen.add(edge)
            children[node].append(edge)
            stack.append(edge)

def solve(node, siblings, depth):
    num_children = len(children[node])

    has_grandparent = depth >= 2
    has_parent = depth >= 1

    ans = max(0, K-(siblings)-int(has_parent)-int(has_grandparent))
    child_siblings = 0
    for child in children[node]:
        ans *=  solve(child, child_siblings, depth+1)
        ans %= MOD
        child_siblings += 1
    return ans


print(solve(1, 0, 0) % MOD)
s = input()
week = ("SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT")

print(7 - index.week(s))

### FIXED CODE ###

s = input()
week = ("SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT")

print(7 - week.index(s))
def check(operate_list, num_list):
    res = num_list[0]
    for i, op in enumerate(operate_list):
        if op == "+":
            res += num_list[i+1]
        elif op == "-":
            res -= num_list[i+1]
    return res == 7

def concat(operate_list, num_list):
    string = num_list[0]
    for op, num in zip(operate_list, num_list[1:]):
        # it is beautiful!
        string += op
        string =+ num
    string += "="
    return string

def main():
    line = sys.stdin.readline().strip()
    num_list = []
    for s in line:
        num_list.append(int(s))
    result = ""
    stack = []
    stack.append([])
    N = len(num_list)
    while(len(stack) != 0){
        l = stack.pop()
        if len(l) == N-1:
            if check(l, num_list):
                result = concat(l, num_list)
                break
        else:
            stack.append(l + ["+"]) # careful code
            stack.append(l + ["-"])
    }
    print(result)


### FIXED CODE ###

import sys

def check(operate_list, num_list):
    res = num_list[0]
    for i, op in enumerate(operate_list):
        if op == "+":
            res += num_list[i+1]
        elif op == "-":
            res -= num_list[i+1]
    return res == 7

def concat(operate_list, num_list):
    num_list = list(map(str, num_list))
    string = num_list[0]
    for op, num in zip(operate_list, num_list[1:]):
        # it is beautiful!
        string += op
        string += num
    string += "=7"
    return string

def main():
    line = sys.stdin.readline().strip()
    num_list = []
    for s in line:
        num_list.append(int(s))
    result = ""
    stack = []
    stack.append([])
    N = len(num_list)
    while(len(stack) != 0):
        l = stack.pop()
        if len(l) == N-1:
            if check(l, num_list):
                result = concat(l, num_list)
                break
        else:
            stack.append(l + ["+"]) # careful code
            stack.append(l + ["-"])

    print(result)

if __name__ == "__main__":
    main()
from collections import deque

queue = deque([])

n = int(input())

for i in range(n):
    commands = input().split(" ")
    command = commands[0]
    if command == "insert":
        queue.appendleft(commands[1])
    elif command == "delete":
        queue.remove(commands[1])
    elif command == "deleteFirst":
        queue.popleft()
    elif command == "deleteLast":
        queue.pop()

last = queue.pop()
for i in queue:
    print(i, end=" ")

print(last)

### FIXED CODE ###

import sys
from collections import deque

queue = deque()

for _ in range(int(sys.stdin.readline())):
    commands = sys.stdin.readline()[:-1].split(" ")
    if commands[0] == "insert":
        queue.appendleft(commands[1])
    elif commands[0] == "delete":
        try:
            queue.remove(commands[1])
        except ValueError:
            pass
    elif commands[0] == "deleteFirst":
        queue.popleft()
    elif commands[0] == "deleteLast":
        queue.pop()

print(" ".join(queue))
import heapq
N, Q = (int(i) for i in input().split())
L = [0] * 2 * N
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, X, 1)
    L[2 * i + 1] = (T-X, X, 0)

L.sort(reverse=True)

Xs = set([])
XH = []
heapq.heapify(XH)
for i in range(Q):
    D = int(input())
    ans = 0
    while True:
        if L:
            t, X, f = L.pop()
            if t <= D:
                if f == 1:
                    Xs.add(X)
                    heapq.heappush(XH, X)
                else:
                    Xs.remove(X)
            else:
                L.append((t, X, f))
                break
        else:
            break
    if Xs:
        while True:
            X = heapq.heappop(XH)
            if X in Xs:
                print(X)
                break
    else:
        print("-1")

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq
N, Q = (int(i) for i in input().split())
L = [0] * (2 * N + Q)
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, 1, X)
    L[2 * i + 1] = (T-X, -1, X)
for i in range(Q):
    D = int(input())
    L[2 * N + i] = (D, 2, 0)
L.sort()

Xs = set([])
XH = []
heapq.heapify(XH)
for t, f, X in L:
    if f == 1:
        Xs.add(X)
        heapq.heappush(XH, X)
    elif  f == -1:
        Xs.remove(X)
    else:
        if Xs:
            while XH[0] not in Xs:
                X = heapq.heappop(XH)
            print(XH[0])
        else:
            print("-1")
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n - 1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def main():
    cost = [[0] * n for _ in range(n)]

    for i in range(len(abc)):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a][b] = c

    graph = csr_matrix(cost)
    dist_matrix = dijkstra(csgraph=graph, directed=False, indices=K-1, return_predecessors=False)

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n - 1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

from heapq import heappop, heappush

def main():
    cost = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    # print(cost)

    start = K - 1
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        for v, weight in cost[u]:
            alt = du + weight
            if d[v] > alt:
                d[v] = alt
                heappush(q, (alt, v))

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()
n = int(input()) #number of meals

return(n*800 - n%15*200)

### FIXED CODE ###

n = int(input()) #number of meals
print(n*800 - n//15*200)
from math import *
from bisect import *
s=input()
t=input()
n=len(s)
nn=len(t)
ss=[[]for i in range(26)]
tt=[[] for i in range(26)]
ans=0
k=0
for i in range(n):
    ss[ord(s[i])-97].append(i+1)
for i in t:
    j=ss[ord(i)-97]
    if len(j)==0:
        print(-1)
        exit()
    else:
        if j[-1]<ans:
            ans=j[0]
            k+=1
        else:
            ans=j[bisect(j,ans)]
print(k*n+ans)

### FIXED CODE ###

from math import *
from bisect import *
s=input()
t=input()
n=len(s)
nn=len(t)
ss=[[]for i in range(26)]
tt=[[] for i in range(26)]
ans=0
k=0
for i in range(n):
    ss[ord(s[i])-97].append(i+1)
for i in t:
    j=ss[ord(i)-97]
    if len(j)==0:
        print(-1)
        exit()
    else:
        if j[-1]<=ans:
            ans=j[0]
            k+=1
        else:
            ans=j[bisect(j,ans)]
print(k*n+ans)
a = input()
b = input()
c = input()
d=[]
alist = list(a)
for i in range(int(c)):
  e = input().split()
  d.append(e)
for i in range(int(c)):
  if d[i][0]=="1":
    l = len(alist)
    for x in range(int(l//2)):
      alist[x],alist[l-x-1] = alist[l-x-1],alist[x]
  else:
    if d[i][1] == "1":
      alist = [d[i][2]] + alist
    else:
      alist = alist + [d[i][2]]
le = len(alist)
answer =""
for i in range(le):
  answer = answer + alist[i]
print(answer)

### FIXED CODE ###

from collections import deque
a = input()
c = input()
d = []
alist = list(a)
adeque = deque(a)
count = 0
for i in range(int(c)):
  e = input().split()
  d.append(e)
for i in range(int(c)):
  if d[i][0]=="1":
    count = count + 1
  else:
    if d[i][1] == "1" and count % 2 == 0:
      adeque.appendleft(d[i][2])
    elif d[i][1] == "2" and count % 2 == 1:
      adeque.appendleft(d[i][2])
    else:
      adeque.append(d[i][2])
alist = list(adeque)
if count % 2 == 1:
  l = len(alist)
  for x in range(int(l//2)):
    alist[x],alist[l-x-1] = alist[l-x-1],alist[x]
answer = "".join(alist)
print(answer)
n= int(input())
branchdict = {}
for i in range(n-1):
    a,b,c= map(int,input().split())
    branchdict[a-1] = branchdict.get(a-1,[]) + [(b-1,c)]
    branchdict[b-1] = branchdict.get(b-1,[]) + [(a-1,c)]
q,k= map(int,input().split())
passed = set()
cost = [0] * n
def dfs(curnode,addcost):
    cost[curnode]=addcost
    passed.add(curnode)
    for abr in branchdict[curnode]:
        if not abr[0] in passed:dfs(abr[0],addcost+abr[1])
dfs(k-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n= int(input())
bd = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c= map(int,input().split())
    bd[a-1].append((b-1,c))
    bd[b-1].append((a-1,c))
q,k= map(int,input().split())
cost = [0] * n
def dfs(curnode,pre,addcost):
    for abr in bd[curnode]:
        if abr[0]!=pre:
            cost[abr[0]]=addcost+abr[1]
            dfs(abr[0],curnode,addcost+abr[1])
dfs(k-1,-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])
from functools import reduce
import math
N, X = map(int, input().split())
x = list(map(int, input().split()))
new_list = list(map(lambda l: abs(l - X), x))
new_list.sort()
gcd = reduce(math.gcd, new_list)
print(gcd)

### FIXED CODE ###

from functools import reduce
from fractions import gcd
N, X = map(int, input().split())
x = list(map(int, input().split()))
new_list = list(map(lambda l: abs(l - X), x))
new_list.sort()
gcd = reduce(gcd, new_list)
print(gcd)
a,b=input().split()
s=input()
print("Yes" if s[a]=="_" and s.count("_")==1 else "No")

### FIXED CODE ###

a,b=input().split()
s=input()
print("Yes" if s[int(a)]=="-" and s.count("-")==1 else "No")
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

def cmb(n, k):
    if k < 0 or k > n: return 0 
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 2 * 10 ** 6 + 2  # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

r1, c1, r2, c2 = lr()
answer = cmb(r2+c2+2, r2+1) - 1
answer -= cmb(r2+c1+1, r2+1) - 1
answer -= cmb(r1+c2+1, c2+1) - 1
answer += cmb(r1+c1, r1) - 1
print(answer % MOD)
# 26

### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def cmb(n, k):
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

r1, c1, r2, c2 = lr()
MOD = 10 ** 9 + 7
U = 2 * 10 ** 6 + 10
fact, fact_inv = make_fact(U,MOD)

answer = cmb(r2+c2+2, r2+1) - cmb(r2+1+c1, r2+1) - cmb(r1+c2+1, r1) + cmb(r1+c1, r1)
print(answer % MOD)

# 16
h, w = list(map(int, input().split()))
sharp = 0
data = []
for i in range(h):
    data.append(list(input()))
    sharp += data[i].count('#')
ans = []
def dfs(row, column, count,data):
    if(row > w - 1) or (column > h - 1) or ( row < 0 ) or ( column < 0 ):
        return

    if data[column][row] == '#':
        return

    data[column][row] = '#'

    if column == h- 1 and row == w - 1:
        count += 1
        ans.append(count)
        return

    else:

        dfs(row + 1, column,     count + 1,data)
        dfs(row,     column + 1, count + 1,data)
        dfs(row - 1, column,     count + 1,data)
        dfs(row,     column - 1, count + 1,data)
        return
dfs(0, 0, 0,data)
if len(ans) == 0:
    k = -1
else:
    k = min(ans)
print(h * w - sharp - k)


### FIXED CODE ###

import collections
h, w = list(map(int, input().split()))
inf = h * w + 1
sharp = 0
data = []
for i in range(h):
    data.append(list(input()))
    # #の数を数えておく
    sharp += data[i].count('#')

ans = [[inf for i in range(w)] for j in range(h)]
def dfs(row, column, count,data):
    #もし配列の外を参照しているようであれば終了させる
    if(row > w - 1) or (column > h - 1) or ( row < 0 ) or ( column < 0 ):
        return

    if data[column][row] == '#':
        return
    data[column][row] == '#'
    #探索済みなので＃を入れたが、もっと良い方法があるかもしれない
    count += 1
    if row == w - 1 and column == h - 1:
        ans[column][row] = min(count, ans[column][row])
        return
    #その場所がゴールならば終了。ansにそこまでのコストを追加
    ##dataの写しを引数として渡したい。参照渡しか値渡しかを確認
    #+-1ずつ四方向に全探索
    dfs(row + 1, column,     count, data)
    dfs(row,     column + 1, count, data)
    dfs(row - 1, column,     count, data)
    dfs(row,     column - 1, count, data)
def bfs(row, column, count,data):
    becter = [-1,1]
    queue = collections.deque()
    queue.append([column, row,count])
    while len(queue) != 0:
        v = queue.popleft()
        if v[0] < 0 or v[1] < 0 or v[0] >= h or v[1] >= w:
            continue
        if data[v[0]][v[1]] != '#':

            data[v[0]][v[1]] = '#'
            v[2] += 1
            ans[v[0]][v[1]] = min(ans[v[0]][v[1]], v[2])
            queue.append([v[0] + 1, v[1],v[2]])
            queue.append([v[0], v[1] + 1,v[2]])
            queue.append([v[0] - 1, v[1],v[2]])
            queue.append([v[0], v[1] - 1,v[2]])


bfs(0, 0, 0,data)
if ans[-1][-1] == inf:
    print(-1)
    exit()
print(h * w - sharp - ans[-1][-1])
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

K=int(input())
S=input()

dp=[[0]*(len(S)+1) for _ in range(K+len(S)+1)]
dp[0][0]=1
for i in range(K+len(S)):
    for j in range(len(S)+1):
        if j==len(S):
            dp[i+1][j]+=dp[i][j]*26
        else:
            dp[i+1][j]+=dp[i][j]*25
        if j+1<=len(S):
            dp[i+1][j+1]+=dp[i][j]
            dp[i+1][j+1]%=MOD
        dp[i+1][j]%=MOD
print(dp[-1][-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

K=int(input())
S=input()

def COMinit(n,MOD):
    fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,(n+1)):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

fac,finv,inv=COMinit(3*10**6,MOD)

def COM(n, k, MOD=MOD):
    if n<k or n<0 or k<0:
        return 0
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD

dp=[[0]*(K+len(S)+1) for _ in range(2)]
for i in range(len(S)-1,K+len(S)+1):
    dp[0][i]=COM(i,i-len(S)+1)*pow(25,i-len(S)+1,MOD)
dp[1][len(S)]
for i in range(K+len(S)):
    dp[1][i+1]=dp[1][i]*26+dp[0][i]
    dp[1][i+1]%=MOD
print(dp[1][-1])
N = int(input())
Lists = map(int,input().split())
sum = 0
for x in Lists:
  sum+=i/x
 
print(i/sum)

### FIXED CODE ###

N = int(input())
Lists = map(int,input().split())
sum = 0
for x in Lists:
  sum+=1/x
 
print(1/sum)