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

import math
N = int(input())
for n in range(1,N+1):
    r_n = math.floor(math.sqrt(n))
    count = 0
    if(n >= 6):
        for x in range(1,r_n):
            y_n = min(r_n,math.floor(math.sqrt(n-x*x)))
            for y in range(1,y_n):
                z_n = min(y_n,math.floor(math.sqrt(n-(x*x+y*y))))
                for z in range(1,z_n):
                    if (x*x + y*y + z*z + x*y + y*z + z*x) == n:
                        count+=1
    print(count)

### FIXED CODE ###

import math
N = int(input())
ans = [0 for _ in range(10050)]
r_n = math.floor(math.sqrt(N))
count = 0
for x in range(1,r_n):
    for y in range(1,r_n):
        for z in range(1,r_n):
            n = x*x + y*y + z*z + x*y + y*z + z*x
            if n < 10050:
                ans[n]+=1
for i in range(N):
    print(ans[i+1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
import functools
import fractions 
# 最小公倍数
def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)
def lcmn(nums):
  return functools.reduce(lcm, nums)
lcma=lcmn(a)
ans=0
mod=pow(10,9)+7
for ai in a:
  ans+=lcma//ai
  ans%=mod
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=pow(10,9)+7

#n=10000
#a=list(range(10**6,10**6-n,-1))

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
lcma={}
for ai in a:
  f=factorization(ai)
  for fi in f:
    if fi[0] in lcma:
      lcma[fi[0]]=max(lcma[fi[0]],fi[1])
    else:
      lcma[fi[0]]=fi[1]
l=1
for k,v in lcma.items():
  l*=pow(k,v,mod)
  l%=mod
ans=0
for ai in a:
  ans+=l*pow(ai,mod-2,mod)
  ans%=mod
print(ans)
### BUGGY CODE ###

n = int(input())

li=list(map(int,input().split()))
count = 0

for i in range(n-1):
  if min(li)==li[-1]:
    count+=1
  li.pop()

print(count+1)



### FIXED CODE ###

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

mymin = a[0]
count = 0

for i in range(len(a)):
  if min(mymin, a[i]) == a[i]:
    mymin = a[i]
    count += 1
    
print(count)
### BUGGY CODE ###

import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				break
		B = B[:bi + 1]
		for i in range(1,len(B) + 1):
			C = list(itertools.combinations(B,i))
			p = 0
			for c in C:
				if sum(c) in fusoku:
					need.append(a)
					z = 1
					break
				if sum(c) >= K:
					p = p + 1 
					if p == len(C):
						iranaiko.append(a)
						z = 1
						break
			if z == 1:
				break
		if z == 0:
			iranaiko.append(a)
print(N - len(need))


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
		if z == 0:
			iranaiko.append(a)

print(N - len(need))
### BUGGY CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

K, N = reads()
MOD = 998244353

MAXN = 5000

fact = [1] * MAXN
for i in range(1, MAXN): fact[i] = (fact[i-1] * i) % MOD
invfact = [0] * MAXN; invfact[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(MAXN-2, -1, -1): invfact[i] = invfact[i+1] * (i+1) % MOD
def comb(n, k):
  return fact[n] * invfact[n-k] * invfact[k] % MOD if 0 <= k <= n else 0
def h(n, k):
  return comb(n+k-1, n) if k >= 1 else 0

def solve(n, k, u):
  ans = 0
  for q in range(u+1):
    s = 2**(u-q) * h(n-u+q, k-q-u)
    # print(n, k, u, q, s)
    ans = (ans + comb(u, q) * pow(2, u-q, MOD) % MOD * h(n-u+q, k-q-u)) % MOD
  return ans

for i in range(2, 2*K+1):
  u = sum(j < i-j <= K for j in range(1, K+1))
  if i % 2 == 1:
    ans = solve(N, K, u)
  else:
    ans = (solve(N, K-1, u) + solve(N-1, K-1, u)) % MOD
  print(ans)

### FIXED CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

K, N = reads()
MOD = 998244353

MAXN = 4020

fact = [1] * MAXN
for i in range(1, MAXN): fact[i] = (fact[i-1] * i) % MOD
invfact = [0] * MAXN; invfact[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(MAXN-2, -1, -1): invfact[i] = invfact[i+1] * (i+1) % MOD
def comb(n, k):
  return fact[n] * invfact[n-k] * invfact[k] % MOD if 0 <= k <= n else 0
def h(n, k):
  return comb(n+k-1, n)

def solve(n, k, u):
  ans = 0
  for q in range(u+1):
    ans = (ans + comb(u, q) * pow(2, u-q, MOD) % MOD * h(n-u+q, k-q-u)) % MOD
  return ans

anss = [0] * (2*K+1)
for i in range(2, K+2):
  u = sum(j < i-j <= K for j in range(1, K+1))
  if i % 2 == 1:
    ans = solve(N, K, u)
  else:
    ans = (solve(N, K-1, u) + solve(N-1, K-1, u)) % MOD
  anss[i] = ans
  print(ans)

for j in range(K+2, 2*K+1):
  print(anss[2*K - j + 2])
### BUGGY CODE ###

A, B = list(map(int, input().split()))
ans = 0
for i in range(A, B+1):
    ans = ans^ i
print(ans)


### FIXED CODE ###

A, B = list(map(int, input().split()))
c = []
c.append(A % 4 // 2 ^ (B + 1) % 4 // 2)

keta = 2
while(B // keta != 0):
    if A // keta % 2 == 0:
        a = 0
    else:
        a = A % keta
    if B // keta % 2 == 0:
        b = 0
    else:
        b = B % keta
        b += 1
    c.append((b - a) % 2)
    keta = keta<<1
ans = 0

for i in range(len(c) - 1, -1, -1):
    ans = ans<<1
    ans ^= c[i]
print(ans)
### BUGGY CODE ###

import bisect
K, S = map(int,input().split())
listK = [i for i in range(K+1)]
ans = 0
for i in range(K+1):
    for j in range(K+1):
        id = bisect.bisect_left(listK,S-i-j)
        if id < len(listK) and listK[id] == S-i-j:
                ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int,input().split())
ans = 0
for x in range(K+1):
    for y in range(K+1):
        z = S-x-y
        if 0 <= z and z <= K:
            ans += 1
print(ans)
### BUGGY CODE ###

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

for j in range(Q):
    b, c = map(int, input().split())

    rep = [i for i in A if i != b]
    for _ in range(len(A) - len(rep)):
        rep.append(c)
    A = rep[::]

    print(sum(A))


### FIXED CODE ###

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

B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

d = [0] * (10**5 + 7)
for a in A:
    d[a] += 1
sum_a = sum(A)
for j in range(Q):
    before = d[C[j]]
    d[C[j]] += d[B[j]]
    sum_a -= d[B[j]] * B[j]

    sum_a += (d[C[j]] - before) * C[j]
    d[B[j]] = 0
    print(sum_a)
### BUGGY CODE ###

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

# 期待値配列
E = [(p+1)/2 for p in P]

# 隣接K個を取り出して足す
max_E = 0
for i in range(N-K+1):
    tmp_E = sum(E[i: i+K])
    if tmp_E > max_E:
        max_E = tmp_E

print(max_E)

### FIXED CODE ###

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

# 期待値
E = [(p+1)/2 for p in P]
#print(E)

# 累積和
S = [0] * (N+1)
for i in range(N):
    S[i+1] = S[i] + E[i]
#print(S)

# 隣接K個を取り出して足す
max_E = 0
for i in range(N-K+1):
    tmp_E = S[i+K] - S[i]
    #print(tmp_E)
    if tmp_E > max_E:
        max_E = tmp_E

print(max_E)
### BUGGY CODE ###

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

if ans>10**18:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

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


if 0 in a:
    print(0)
else:
    ans=1
    i=0
    while ans<=10**18 and i<n:
        ans*=a[i]
        i+=1

    if ans>10**18:
        print("-1")
    else:
        print(ans)
### BUGGY CODE ###

k = int(input())
seven = 7
ans = 1

if k % 2 == 0:
    ans = -1
elif k == 1 or k == 7:
    ans = 1
else:
    while seven % k != 0:
        seven = seven * 10 + 7
        ans += 1

print(ans)


### FIXED CODE ###

k = int(input())
seven = 7
ans = -1

for i in range(1,k+1):
    seven %= k
    if seven  == 0:
        ans = i
        break
    else:
        seven = seven * 10 + 7

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

# input
N = int(input())
As = list(map(int, input().split()))

# Nの偶奇。区間幅がNの偶奇と一致すれば太郎君目線
oe = N % 2

# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[[None for _ in range(2)] for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ0であれば1通りしかない
  score[i][i][0] = As[i]
  score[i][i][1] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(0, N-k):
    # if k == 0:
    #   continue
    j = i + k
    if i == N - 1:
      if (k + 1) % 2 == oe:
        score[i][j][0] = score[i][j-1][1] + As[j]
      else:
        score[i][j][1] = score[i][j-1][0] - As[j]
    else:
      # print(i,j)
      if (k + 1) % 2 == oe:
        score[i][j][0] = max(score[i+1][j][1] + As[i], score[i][j-1][1] + As[j])
      else:
        score[i][j][1] = min(score[i+1][j][0] - As[i], score[i][j-1][0] - As[j])
    # print_list(score)

print(score[0][N-1][0])


### FIXED CODE ###

# input
N = int(input())
As = list(map(int, input().split()))

# Nの偶奇。区間幅がNの偶奇と一致すれば太郎君目線
oe = N % 2

# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[None for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ1であれば1通りしかない
  if oe == 1:
    score[i][i] = As[i]
  else:
    score[i][i] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(0, N-k):
    # if k == 0:
    #   continue
    j = i + k
    if i == N - 1:
      if (k + 1) % 2 == oe:
        score[i][j] = score[i][j-1] + As[j]
      else:
        score[i][j] = score[i][j-1] - As[j]
    else:
      # print(i,j)
      if (k + 1) % 2 == oe:
        score[i][j] = max(score[i+1][j] + As[i], score[i][j-1] + As[j])
      else:
        score[i][j] = min(score[i+1][j] - As[i], score[i][j-1] - As[j])
    # print_list(score)

print(score[0][N-1])
### BUGGY CODE ###

n = int(input())
L = [input() for _ in range(n)]
s = sorted(set(L))
c = [0] * len(s)
for i in range(len(s)):
    c[i] = L.count(s[i])
m = max(c)
for j in range(len(c)):
    if c[j] == m:
        print(s[j])

### FIXED CODE ###

n = int(input())
L = sorted(input() for _ in range(n))
s = sorted(set(L))
c = [0] * len(s)
prev = L[0]
cnt = 1
l = 0
for i in range(1, len(L)):
    if L[i] == prev:
        cnt += 1
    else:
        c[l] = cnt
        l += 1
        cnt = 1
        prev = L[i]
c[-1] = cnt
m = max(c)
for j in range(len(c)):
    if c[j] == m:
        print(s[j])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
am = max(a)
ans = 0
for i in range(n-1):
    for j in range(i+a[i], min(n, i+a[i]+am+1)):
        if j-i == a[i]+a[j]:
            ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
L = {}
R = {}
for i in range(n):
    if i+a[i] in L:
        L[i+a[i]].append(i)
    else:
        L[i+a[i]] = [i]
    if i-a[i] in R:
        R[i-a[i]].append(i)
    else:
        R[i-a[i]] = [i]
for i in range(n):
    if i in L and i in R:
        ans += len(L[i])*len(R[i])
print(ans)
### BUGGY CODE ###



K,N = list(map(int,input().split()))
A = list(map(int,input().split()))
A.append(K)
B = []
for i in range(N):
    B.append(abs(A[i]-A[i+1]))
#print(B)
ans = K
for i in range(N):
    ans = min(ans,sum(B)-B[i])
print(ans)


### FIXED CODE ###



K,N = list(map(int,input().split()))
A = list(map(int,input().split()))
B = []
for i in range(N-1):
    B.append(abs(A[i+1]-A[i]))
B.append(K+A[0]-A[-1])
#print(B)
print(K-max(B))
### BUGGY CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return sum(range(1,n+1)) / n
 
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
elif K == 1:
  print(E(max(l)))
else:
  j = sum(l[0:0+K])
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))

### FIXED CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return (1 + n) / 2
 
j = sum(l[0:0+K])
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
else:
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))
### BUGGY CODE ###

# 初期入力
#棒を長さでソートし、
N = int(input())
L = list(map(int, input().split()))
L_sorted =sorted(L)

#3本選ぶ組み合わせ,1番長いもの2本決めると、短いものは最低の長さが決まる=0
import bisect

count =[]
for i in range(N-1,1,-1): #一番長い
    for j in range(i-1,0,-1):#真ん中
        x =L_sorted[i] - L_sorted[j]
        index =bisect.bisect_right(L_sorted,x,lo=0,hi=j)
        a=0
        #if 0<=index +a and index + a <= N:
        count.append(j-(index+a))
            #print(L_sorted[i],L_sorted[j],L_sorted[index+a],index,x)

print(sum(count))

### FIXED CODE ###

import bisect

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

count  =0
L.sort()
for i in range(0, N - 1):
  for j in range(i + 1, N):
    index = bisect.bisect_left(L, L[i] + L[j]) #AC:約2.9秒
    count += max(0, index - j - 1)

"""
    失敗:回答は出るがTLE:ランダム配列1000本で約6.2秒
    index = bisect.bisect_left(L[j+1:],L[i] + L[j]) #TLEの原因?
    count += index
"""
print(count)
### BUGGY CODE ###

import sys
from collections import defaultdict, deque

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = map(int, input().split())
        for sum_w in range(W, w-1, -1):
            if sum_w - w >= 0:
                dp[sum_w] = max(dp[sum_w], dp[sum_w - w] + v)
    print(dp[-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict, deque

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [0] * (W + 1)


    for _ in range(N):
        w, v = map(int, input().split())
        for sum_w in range(W, w-1, -1):
            tv = dp[sum_w - w] + v
            if tv > dp[sum_w]:
                dp[sum_w] = tv
    print(dp[-1])

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

n = int(input())

a = 0

while (True):
    a += n % 10
    n = n // 10
    if n == 0:
        break

if a % 9 == 0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

n = input()
a = 0

for i in n:
    a += int(i)

if a % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N = int(input())
Ex = [False for i in range(1000000001)]
for i in range(N):
	A = int(input())
	Ex[A] = not Ex[A]
count = 0
for tf in range(1000000001):
	if Ex[tf]:
		count += 1
print(count)

### FIXED CODE ###

N = int(input())
ans = {}
for i in range(N):
  ai = int(input())
  if ans.get(ai):
    ans.pop(ai)
  else:
    ans[ai] = 1
print(len(ans))
### BUGGY CODE ###

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

def sm(lst, j, k):
  res = 0
  for i in range(j, j+k):
    res += lst[i]
  return res

def max(lst, k):
  res = sm(lst, 0, k)
  for i in range(1, N-k+1):
    if lst[i-1] < lst[i+k-1]:
      if res < sm(lst, i, k):
        res = sm(lst, i, k)
  res = (res+k)/2
  return res

print(max(List, K))

### FIXED CODE ###

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

def sm(lst, j, k):
  return lst[j+k]-lst[j]

def max(lst, k):
  sumlst = [0]
  for i in range(len(lst)):
    sumlst.append(sumlst[i]+lst[i])
  res = 0
  for i in range(N-k+1):
    if res < sm(sumlst, i, k):
      res = sm(sumlst, i, k)
  res = (res+k)/2
  return res

print(max(List, K))
### BUGGY CODE ###

import networkx as nx

N = int(input())

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

G = nx.Graph()

color = [0 for _ in range(N)]  # 0: tbd，1: white, 2: black

for u, v, w in UVW:
    G.add_edge(u - 1, v - 1, weight=w)

color[0] = -1

for i in range(N - 1):
    for j in range(i + 1, N):
        if color[j] == 0:
            d = nx.shortest_path_length(G, source=i, target=j, weight="weight")
            if int(d + 0.5) % 2 == 0:
                color[j] = color[i]
            else:
                color[j] = color[i] * -1

ans = [1 if i == -1 else 0 for i in color]
print(*ans)


### FIXED CODE ###

import networkx as nx

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

G = nx.Graph()

color = [0 for _ in range(N)]

for u, v, w in UVW:
    G.add_edge(u - 1, v - 1, weight=w)

color[0] = -1

pred, dist = nx.dijkstra_predecessor_and_distance(G, 0)

c = [dist[i] for i in range(N)]
ans = [1 if i % 2 == 0 else 0 for i in c]
print(*ans)
### BUGGY CODE ###


def nCr(n,r):
  if n < 0 or r < 0 or n < r: return 0
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n
  
  # 分子のn*(n-1)*...がr個分続くやつ
  numerator = [n-r+k+1 for k in range(r)]
  # 分母：r!=r*(r-1)*...*3*2の要素
  denominator = [k+1 for k in range(r)]
  
  # 分母の要素で割れる部分を割っていく部分
  for p in range(2, r+1):
    # 分母は1,2,3,...rのようになっており、1は意味がないのでスキップした形か
    pivot = denominator[p-1]
    if pivot > 1:
      # 分子のX番目と分母のX-offset番目が共通の約数を持つということだと思う。piv分ずれているのだから、pivの倍数というところか
      offset = (n-r) % p
      for k in range(p-1, r, p):
        # 約分できる要素について割る
        numerator[k - offset]  /= pivot
        denominator[k] /= pivot
        
  ret = 1
  for k in range(r):
    if numerator[k] > 1: ret *= int(numerator[k])
      
  return ret

N,K = map(int, input().split())
MOD = 10**9+7
A = list(map(int, input().split()))
A.sort()

if N == 1 or K == 1:
    print(0)
    exit()

# A_iがminに選ばれる回数と、maxに選ばれる回数それぞれをわけて考えて足していく
ans = 0
for i in range(N):
    # minになれるのは、iの右からK-1個選べる場合
    if N - (i+1) >= K-1:
        ans -= A[i] * nCr(N - (i+1), K-1) % MOD
    # maxになれるのは、iの左からK-1個選べる場合
    if i >= K-1:
        ans += A[i] * nCr(i, K-1) % MOD

    ans %= MOD

print(ans)

### FIXED CODE ###


N,K = map(int, input().split())
MOD = 10**9+7
A = list(map(int, input().split()))
A.sort()




if N == 1 or K == 1:
    print(0)
    exit()


def nCr(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    # nCr = n!  / (r! * (n-r)!)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = MOD
#N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    # (a * b * c) % MOD = (a * b % MOD) * c % MOD みたいなやつを利用して、大きな値にならないように一ステップごとにMODをとる
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

# A_iがminに選ばれる回数と、maxに選ばれる回数それぞれをわけて考えて足していく
ans = 0
for i in range(N):
    # minになれるのは、iの右からK-1個選べる場合
    if N - (i+1) >= K-1:
        ans -= A[i] * nCr(N - (i+1), K-1, MOD)
    # maxになれるのは、iの左からK-1個選べる場合
    if i >= K-1:
        ans += A[i] * nCr(i, K-1, MOD)

    ans %= MOD

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

N, P = map(int,input().split())
S = str(input())
L = len(S)
ans = 0
dic = {0:1} #一番右端は0なのでこれは常に必要
now = 0
if P == 2 or P == 5:
  kotae = 0
  for i in range(L):
    if int(S[L-1-i])%P == 0:
      kotae += L-i
  print(kotae)
  exit(0)
else:
  for i in range(L):
    now += int(S[L-1-i])*pow(10,i)
    temp = now%P
    if temp not in dic:
      dic[temp] = 1
    else:
      dic[temp] += 1
#print(dic)
ans = 0  
for i in dic.values():
  if i != 1:
    ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

N, P = map(int,input().split())
S = str(input())
L = len(S)
ans = 0
dic = {0:1} #一番右端は0なのでこれは常に必要
now = 0
if P == 2 or P == 5:
  kotae = 0
  for i in range(L):
    if int(S[L-1-i])%P == 0:
      kotae += L-i
  print(kotae)
  exit(0)
else:
  for i in range(L):
    now += int(S[L-1-i])*pow(10,i,P)
    temp = now%P
    if temp not in dic:
      dic[temp] = 1
    else:
      dic[temp] += 1
#print(dic)
ans = 0  
for i in dic.values():
  if i != 1:
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
st = input()
i = 0
b = 0
w = 0
ans = []
a = 0

for i in range(n + 1):
    for j, s in enumerate(st):
        if i <= j and s == '.':
            a += 1
        elif i > j and s == '#':
            a += 1

    ans.append(a)
    a = 0

print(min(ans))

### FIXED CODE ###

n = int(input())
s = input()
b = [0] * (n + 1)
w = [0] * (n + 1)

for i in range(n):
    if s[i] == '#':
        b[i + 1] = b[i] + 1
    else:
        b[i + 1] = b[i]

for i in range(n - 1, -1, -1):
    if s[i] == '.':
        w[i] = w[i + 1] + 1
    else:
        w[i] = w[i + 1]

ans = [vb + vw for vb, vw in zip(b, w)]
print(min(ans))
### BUGGY CODE ###

S=input()
Q=int(input())
Rev=True
front=''
back=''
for i in range(Q):
    a=input()
    if a=='1':
        Rev=not(Rev)
    else:
        b,c,x=a.split()
        if c == '1':
            if Rev:
                front += x
            else:
                back += x
        else:
            if Rev:
                back += x
            else:
                front += x
if Rev:
    print(front[::-1] + S + back)
else:
    print(back[::-1]+S[::-1]+front)


### FIXED CODE ###

S=input()
Q=int(input())
Rev=True
front=''
back=''
for i in range(Q):
    a=input()
    if a=='1':
        Rev=not(Rev)
    else:
        b,c,x=a.split()
        if c == '1':
            if Rev:
                front += x
            else:
                back += x
        else:
            if Rev:
                back += x
            else:
                front += x
if Rev:
    print(front[::-1] + S + back)
else:
    print(back[::-1]+S[::-1]+front)
### BUGGY CODE ###

from itertools import *
from collections import *
h,w=map(int,input().split())
a=[]
l=[(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    t=list(input())
    a.append(t)
ans=[[float("inf")]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            ans[i][j]=0
            q.append((i,j))
aa=0
while q:
    x,y=q.popleft()
    for xx,yy in l:
        nx,ny=x+xx,y+yy
        if 0<=nx<h and 0<=ny<w:
            if ans[nx][ny]>ans[x][y]+1:
                ans[nx][ny]=ans[x][y]+1
                if ans[nx][ny]>aa:
                    aa=ans[nx][ny]
                if (nx,ny) not in q:
                    q.append((nx,ny))
print(aa)

### FIXED CODE ###

from collections import deque
H,W=map(int, input().split())
 
A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0
 
d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)
print(ans)