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

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

for i in range(Q):
    lq,rq = map(int,input().split())
    s = S[lq-1:rq]
    count = 0
    while(s.find('A') != -1):
        j = s.find('A')
        if(s[j:j+2] == 'AC'):
            count+=1
            s = s[j+2:]
        else:
            s = s[j+1:]
    print(count)


### FIXED CODE ###

"""
N,Q = map(int,input().split())
S = input()

for i in range(Q):
    lq,rq = map(int,input().split())
    s = S[lq-1:rq]
    count = 0
    while(s.find('A') != -1):
        j = s.find('A')
        if(s[j:j+2] == 'AC'):
            count+=1
            s = s[j+2:]
        else:
            s = s[j+1:]
    print(count)
"""
#愚直なやり方だとTLEになってしまう。
#累積和とよばれるテクニックを使う
#https://qiita.com/drken/items/56a6b68edef8fc605821#問題-3-atcoder-abc-122-c---get-ac

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

#区間配列
a = [0] * len(S)
#累積和配列
s = [0] * (len(S) +1)

#左がAである文字Cは何番目にあるか求める
for i in range(len(S)):
    if S[i] == 'C':
        if S[i-1] == 'A':
            a[i] = 1 #i番目に'AC'のCがある (添字が0から始まるため実際にはi-1番目 i番目は'A')

#累積和を計算する
for i in range(1,len(a)+1):
    s[i] = s[i-1] + a[i-1]

#区間内にその文字があるか求める

for i in range(Q):
    lq,rq = map(int,input().split())
    print(s[rq] - s[lq])
### BUGGY CODE ###

h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True for _ in range(w+2)])

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))

round = -1
while prev:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
    prev = next

print(round)


### FIXED CODE ###

import functools as ft

h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True]*(w+2))

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))



round = -1
while prev:
    round += 1
    #print(prev)
    #print(mat)
    def calc(next, tup):
        x = tup[0]
        y = tup[1]
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
        return next
    next = ft.reduce(calc, prev, [])

    prev = next

print(round)
### BUGGY CODE ###

def solve():
    n=int(input())
    count=0
    scount=0
    listcount=0
    anslist=[]
    s=[]
    for i in range(n):
        a=input()
        s.append(a)
    s_count=s.count
    s.sort()
    for i in range(n):
        if listcount==n:
            break
        scount=s_count(s[listcount])
        if scount>count:
            count=scount
            anslist.clear()
            anslist.append(s[listcount])
        elif scount==count:
            anslist.append(s[listcount])
        listcount+=scount
    anslist.sort()
    for i in range(len(anslist)):
        print(anslist[i])
solve()


### FIXED CODE ###

from collections import Counter
n=int(input())
list=[input() for _ in range(n)]
list.sort()
c=Counter(list).most_common()
most=c[0][1]
c.sort()
for i in range(len(c)):
    if c[i][1]==most:
        print(c[i][0])
### BUGGY CODE ###

mod = 10**9 + 7
n = int(input())
A = list(map(lambda x:int(x) % mod, input().split()))

out = 0
for i in range(n - 1):
    for j in range(n - i - 1):
        k = i + j + 1
        # print(A[i], A[k])
        out += ((A[i] % mod) * (A[k] % mod))
        out %= mod
print(out)

### FIXED CODE ###

mod = 10**9 + 7
n = int(input())
A = list(map(lambda x: int(x) % mod, input().split()))

# out = 0
# for i in range(n - 1):
#     for j in range(n - i - 1):
#         k = i + j + 1
#         # print(A[i], A[k])
#         out += (A[i] * A[k])
#         out %= mod
B = A[1:n]
B_s = 0
for i in range(n - 1):
    B_s += B[i] % mod

out = 0
for i in range(n - 1):
    out += A[i] * B_s
    out %= mod
    B_s -= A[i + 1]
    B_s %= mod
    if B_s < 0:
        B_s += mod

print(out)
### BUGGY CODE ###

N, M = map(int, input().split())
A = set(i//2 for i in map(int, input().split()))
m = max(A)
A.remove(m)
base = 0
for i in range(m,M+1,2*m):
	semi = True
	for j in A:
		if i not in range(j,M+1,2*j):
			semi = False
			break
	if semi:
		base = i
		break
if base == 0:
	print(0)
else:
	print(((M // base) + 1)//2)

### FIXED CODE ###

N, M = map(int, input().split())
A = set(i//2 for i in map(int, input().split()))
B = []
for i in A:
	B = B + [0]
	while i % 2 == 0:
		i //= 2
		B[-1] += 1
if len(set(B)) == 1:
	m = max(A)
	A.remove(m)
	base = 0
	for i in range(m,M+1,2*m):
		semi = True
		for j in A:
			if i % j != 0 or (i // j) % 2 == 0:
				semi = False
				break
		if semi:
			base = i
			break
	if base == 0:
		print(0)
	else:
		print(((M // base) + 1)//2)
else:
	print(0)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.tree = [0]*(n+1)
            self.size = n
        
        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i
        
        def sum(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s

    N,Q = map(int,input().split())
    bit = BIT(N)
    C = list(map(int,input().split()))
    query = []
    for i in range(Q):
        l,r = map(int,input().split())
        query.append([l,r,i])
    query.sort(key=lambda x: x[1])
    ans = []
    #良い玉のindexを1-indexで管理する
    colorMemo = [0]*(N+1)
    cur = 1
    for q in query:
        l,r,j = q
        #良い玉の情報を更新する
        for i in range(cur,r+1):
            c = C[i-1]
            if colorMemo[c]:
                bit.add(colorMemo[c],-1)
            bit.add(i,1)
            colorMemo[c] = i
        cur = r + 1
        ans.append([j,bit.sum(r)-bit.sum(l-1)])

    ans.sort()
    for a in ans:
        print(a[1])
main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.tree = [0]*(n+1)
            self.size = n
        
        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i
        
        def sum(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s

    N,Q = map(int,input().split())
    bit = BIT(N)
    C = list(map(int,input().split()))
    query = []
    for i in range(Q):
        l,r = map(int,input().split())
        query.append([l,r,i])
    query.sort(key=lambda x: x[1])
    ans = [0]*Q
    #良い玉のindexを1-indexで管理する
    colorMemo = [0]*(N+1)
    cur = 1
    for q in query:
        l,r,j = q
        #良い玉の情報を更新する
        for i in range(cur,r+1):
            c = C[i-1]
            if colorMemo[c]:
                bit.add(colorMemo[c],-1)
            bit.add(i,1)
            colorMemo[c] = i
        cur = r + 1
        ans[j]=bit.sum(r)-bit.sum(l-1)

    print(*ans, sep="\n")
main()
### BUGGY CODE ###

N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        t1 = 4 * h * n
        t2 = N * (h+n)
        if t1 != t2:
            temp = (N*h*n) / (t1-t2)
            if temp.is_integer():
                if temp > 0:
                    print(h,n,int(temp))
                    break
    else:
        continue
    break

### FIXED CODE ###

N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        t1 = 4 * h * n
        t2 = N * (h+n)
        if t1 != t2:
            temp = (N*h*n) / (t1-t2)
            if temp.is_integer():
                if temp > 0:
                    print(h,n,int(temp))
                    break
    else:
        continue
    break
### BUGGY CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
# nums = [0]*(N+1)
last = 0
for i in range(N):
    m = 10**(N-i-1)%MOD
    # val = (int(S[i])*m + nums[i])%MOD
    val = (int(S[i])*m + last)%MOD
    last = val
    # cnt += d[val]
    d[val] += 1

cnt = 0
for i, v in d.items():
    cnt += v*(v-1)//2
print(cnt)

### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
# nums = [0]*(N+1)
m = 0
last = 0
dd = 1
for i in range(N):
    m += int(S[N-i-1])*dd
    m %= MOD
    # val = (int(S[i])*m + nums[i])%MOD
    # cnt += d[val]
    dd = (dd*10)%MOD
    d[m] += 1

cnt = 0
for i, v in d.items():
    cnt += v*(v-1)//2
print(cnt)
### BUGGY CODE ###

n, k, q = map(int, input().split())
point = [k for _ in range(n)]
for i in range(q):
    point = list(map(lambda x: x-1, point))
    idx = int(input()) - 1
    point[idx] += 1
for j in range(n):
    if point[j] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
point = [k-q for _ in range(n)]
for i in range(q):
    idx = int(input()) - 1
    point[idx] += 1
for j in range(len(point)):
    if point[j] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
         
number_of_items=[]
for X in range(min(A)-1, max(A)+1):
    number_of_items.append(A.count(X)+A.count(X-1)+A.count(X+1))
print(max(number_of_items))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
bucket=[0]*(max(A)+1)
answer=0
for number in A:
    bucket[number]+=1
if len(bucket)<3:
    answer=sum(bucket)
for i in range(1,max(A)):
    candidate=bucket[i-1]+bucket[i]+bucket[i+1]
    if candidate>answer:
        answer=candidate
print(answer)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
order_list = []
for i in range(1, N+1):
  order_list.append(A.index(i)+1)
print(*order_list)

### FIXED CODE ###

N = int(input())
A = map(int, input().split())
order_list = []
for i,a in enumerate(A,1):
  order_list.append((i,a))
order_list.sort(key=lambda x:x[1])
print(' '.join(str(ans[0]) for ans in order_list))
### BUGGY CODE ###

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

count = 0
for i in range(0,K+1):
    for j in  range(0,K+1):
        for k in  range(0,K+1):
            if i + j + k == S:
                count += 1
print(count)

### FIXED CODE ###

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

count = 0
for i in range(0,K+1):
    if i > S:
        continue
    for j in  range(0,K+1):
        if 0 <= (S - i - j) <= K:
            count += 1

print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
out = []
for i in range(1, N+1):
    if i not in A:
        out.append(0)
    else:
        out.append(A.count(i))
for a in out:
  print(a)


### FIXED CODE ###

import collections

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

c = collections.Counter(A)

for i in range(1, N+1):
    if i not in c:
        print(0)
    else:
        print(c[i])
### BUGGY CODE ###

N =int(input())
s = list(sorted(input()) for i in range(N))
cnt = 0
for i in range(N):
    for j in range(N):
        if s[i]==s[j]:
            cnt+=1
print(int((cnt-N)/2))

### FIXED CODE ###

import collections

N =int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
cnt = 0
ans =0
for i in set(s):
    cnt = c[i]
    ans += cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

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

a = [i for i in a if i <k]
n = len(a)

DP1 = [[False]*(k+1)]
DP1[0][0] = True
DP2 = [[False]*(k+1)]
DP2[0][0] = True
b = a[::-1]

for i in range(n):
    DP1.append(DP1[i][:])
    DP2.append(DP2[i][:])
    for j in range(k+1):
        if DP1[i][j] and a[i]+j <= k:
            DP1[i+1][a[i]+j] = True
        if DP2[i][j] and b[i]+j <= k:
            DP2[i+1][b[i]+j] = True

for i in range(n+1):
    q = [0]
    for j in range(k+1):
        q.append(q[-1]+int(DP2[i][j]))
    DP2[i] = q

ans = 0
for i in range(n):
    use = False
    for j in range(k+1):
        if not DP1[i][j]:
            continue
        left = max(0, k-a[i]-j)
        right = k-j
        if DP2[n-i-1][right] - DP2[n-i-1][left]:
            use = True
            break
    if not use:
        ans += 1

print(ans)

### FIXED CODE ###

import numpy as np

def main():
    def check(m):
        DP = np.full(k+1, False)
        DP[0] = True
        for i in range(n):
            if i == m:
                continue
            DP[a[i]:] = np.logical_or(DP[a[i]:], DP[:k+1-a[i]])
        return any(DP[i] for i in range(k-a[m], k))

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

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    left = -1
    right = n

    while right-left > 1:
        mid = (right+left)//2
        if check(mid):
            right = mid
        else:
            left = mid

    print(right)

main()
### BUGGY CODE ###

s = input()
k = int(input())

array = set()
n = len(s)

for i in range(n):
    for j in range(i + 1, n + 1):
        ss = s[i:j]
        array.add(ss)
        if len(array) > k:
            array = sorted(array)
            array.pop()
            array = set(array)

array = sorted(array)
print(array[k - 1])


### FIXED CODE ###

s = input()
k = int(input())

n = len(s)
array = []

for i in range(n):
    for j in range(i + 1, i + 6):
        end = min(n, j)
        ss = s[i:end]
        array.append(ss)

array = set(array)
array = sorted(array)
print(array[k - 1])
### BUGGY CODE ###

import sys
from fractions import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    l=A[0]
    for x in A[1:]:
        l=l*x//gcd(l,x)
    ans=0
    for x in A:
        ans+=l//x
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from fractions import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    def modinv(a, mod):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    N=int(input())
    A=list(map(int,input().split()))
    l=A[0]
    for x in A[1:]:
        l=l*x//gcd(l,x)
    l%=MOD
    ans=0
    for x in A:
        ans+=l*modinv(x,MOD)
        ans%=MOD
    print(ans)

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

def solve(ls) -> int:
  n = len(ls)
  assert(3 <= n <= 2 * 10**3)

  ret = 0

  ia, ib, ic = (0, 1, 1)
  while True:
    # index adjustment
    ic = ic + 1
    if ic == n:
      ib, ic = (ib + 1, ib + 2)
      if ic == n:
        ia, ib, ic = (ia + 1, ia + 2, ia + 3)
    # index check
    if ic == n:
      break

    a, b, c = (ls[ia], ls[ib], ls[ic])
    if a < b + c and b < c + a and c < a + b:
      ret += 1

  return ret


n = int(input().strip())
ls = [int(l) for l in input().split()]

print(solve(ls))


### FIXED CODE ###

import bisect


def solve(ls) -> int:
  n = len(ls)
  assert(3 <= n <= 2 * 10**3)

  def n_possible_cs(a: int, b: int, first_ic: int) -> int:
    # def bin_search_le_rightmost(s: int, e: int, target: int):
    #   if s == e:
    #     if ls[s] > target:
    #       return None
    #     else:
    #       return s
    #
    #   mid = s + (e - s) // 2
    #
    #   if ls[mid] <= target and (mid + 1 < n and ls[mid + 1] > target):
    #     return mid
    #   elif ls[mid] <= target:
    #     return bin_search_le_rightmost(mid + 1, e, target)
    #   else:
    #     return bin_search_le_rightmost(s, mid, target)

    idx = bisect.bisect_left(ls, a + b, first_ic)
    return 0 if idx == first_ic else idx - first_ic

  ret = 0
  for ia in range(0, n - 2):
    for ib in range(ia + 1, n - 1):
      a, b = (ls[ia], ls[ib])
      x = n_possible_cs(a, b, ib + 1)
      ret += x
  return ret


n = int(input().strip())
ls = [int(l) for l in input().split()]

print(solve(sorted(ls)))
### BUGGY CODE ###

N=int(input())
X=[]
for i in range(20000000):
    X.append(N%10)
    N=N//10
    if N<1:
        break
sumX=sum(X)
if sumX%9==0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N=int(input())
if N%9==0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

import math
import copy

n, m=map(int, input().split())
t = {}
a = int(math.sqrt(m))

s=0

while s==0:
    for i in range(2, a+2):
#         print(i, m)
        cnt = 0
        while m%i==0:
            m=m//i
            cnt += 1

        if cnt>0:
                t[i]=cnt

        if m==1:
            s=1
            break

def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) 

out=1
for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
    out = out%(1000000007)
print(out%(1000000007))

### FIXED CODE ###

import math

n, m=map(int, input().split())
t = {}
a = int(math.sqrt(m))

s=0

line = [2, 3] + [i%2*2 + i//2 * 6 + 5 for i in range(a)]
# line = [2] + list(range(3, m+2, 2))

for i in line:
# for i in range(2, m+2, 2):
#     print(i)
    cnt = 0
    while m%i==0:
        m=m//i
        cnt += 1

    if cnt>0:
        t[i]=cnt

    if m==1:
        break

if m!=1:
    t[m]=1

def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) 

out=1
for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
#     out = out%(1000000007)
print(out%(1000000007))
### BUGGY CODE ###

def solve(i,m):
    global n
    global A
    if m == 0 :
        return True
    elif i >= n :
        return False
    else:
        return (solve(i+1,m) or solve(i+1,m-A[i]))

global n
global A
n = int(input())
st = input()
A = list(map(int,st.split()))
input()     # don't use q(num of ans pattern) dumping!
st = input()
ans = list(map(int,st.split()))

for x in ans:
    if(solve(0,x) == True):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

is_able_make = [False]*2000

input()

A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
q = int(input())
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]

for i in A:
    for j in range(2000-i,0,-1):
        if is_able_make[j] == True:
            is_able_make[i+j] = True
    is_able_make[i] = True

for x in M:
    if(is_able_make[x] == True):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

K,S = map(int,input().split())
patterns = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z == S:
                patterns += 1
print(patterns)

### FIXED CODE ###

K,S = map(int,input().split())
patterns = 0

# # arr = [[x+y for y in range(min(S-x+1,K+1))] for x in range(K+1)]
# farr = list(chain.from_iterable(arr))
# for z in farr:
#     temp_z = S - z
#     if temp_z <= K and temp_z >=0:
#         patterns += 1
# print(farr)
# print(farr.count(S))

for x in range(K+1):
    for y in range(max(0,S-K-x), min(K+1,S-x+1)):
        patterns += 1
print(patterns)
### BUGGY CODE ###

a,b,x = list(map(int,input().split()))
ans = 0
for i in range(a,b+1):
  if i%x == 0:
    ans += 1
print(ans)

### FIXED CODE ###

a,b,x = list(map(int,input().split()))
ax = (a-1)//x
bx = b//x

print(bx-ax)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc098/tasks/arc098_a
# C - Attention
import collections

N = int(input().split()[0])
S = input().split()[0]
min_c = float('inf')
for i in range(N):
    w_side = S[:i]
    counter = collections.Counter(w_side)
    c = counter['W']

    if i < N - 1:
        e_side = S[i+1:]
        counter = collections.Counter(e_side)
        c += counter['E']
    min_c = min(min_c, c)

print(min_c)


### FIXED CODE ###

# https://atcoder.jp/contests/abc098/tasks/arc098_a
# C - Attention
import collections

N = int(input().split()[0])
S = input().split()[0]
min_c = float('inf')
count_dict = {}
now_w = 0
w_count_list = []

for i in range(N):
    w_count_list.append(now_w)
    if S[i] == 'W':
        now_w += 1

now_e = 0
e_count_list = []
r_S = list(reversed(S))
for i in range(N):
    e_count_list.append(now_e)
    if r_S[i] == 'E':
        now_e += 1

e_count_list = list(reversed(e_count_list))

ans = min([w + e for w, e in zip(w_count_list, e_count_list)])
print(ans)
### BUGGY CODE ###

import numpy as np
from collections import deque

h, w = map(int, input().split())
#sy, sx = map(int, input().split())
#gy, gx = map(int, input().split())
map = [input() for _ in range(h)]

f_inf = float('inf')
visited = np.array([[f_inf] * w for _ in range(h)])
que = deque([])
for i in range(h):
    for j in range(w):
        if map[i][j] == "#":
            visited[i][j] = 0
            que.append([i, j])

while que:
    y, x = que.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y, next_x = y + i, x + j
        if next_y > -1 and next_x > -1 and next_y < h and next_x < w and map[next_y][next_x] == ".":
            if visited[next_y][next_x] > visited[y][x] + 1:
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])

print(int(np.max(visited)))


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

cnt = [[-1]*W for _ in range(H)]

que = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            que.append((h, w))
            cnt[h][w] = 0

ans = 0
while que:
    h, w = que.popleft()
    ans = cnt[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        next_h = h + dy
        next_w = w + dx
        if next_h < 0 or H <= next_h or next_w < 0 or W <= next_w:
            continue
        if cnt[next_h][next_w] == -1:
            cnt[next_h][next_w] = ans+1
            que.append((next_h, next_w))

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

N = int(input())

power = 1
for i in range(1, N + 1):
    power *= i
print(power % (10**9 + 7))


### FIXED CODE ###

import math
N = int(input())

print(math.factorial(N) % (10 ** 9 + 7))