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

from copy import deepcopy

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

for _ in range(k):
    if sum(As) == n * n:
        break
    As_next = [0] * n
    for i in range(n):
        for j in range(max(0, i - As[i]), min(n, i + As[i] + 1)):
            As_next[j] += 1
    As = deepcopy(As_next)

print(" ".join(map(str, As)))


### FIXED CODE ###

from copy import deepcopy

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

for _ in range(k):
    if sum(As) == n * n:
        break
    Bs = [0] * n
    for i in range(n):
        l = max(0, i - As[i])
        r = min(n - 1, i + As[i])
        Bs[l] += 1
        if r + 1 < n:
            Bs[r + 1] -= 1
    for i in range(1, n):
        Bs[i] += Bs[i - 1]
    As = Bs

print(" ".join(map(str, As)))
### BUGGY CODE ###

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

cnt = 0
for i in range(1,N+1):
    if min(P[:i]) == P[i-1]:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

mi = P[0]
cnt = 1
for i in range(1,N):
    if P[i] <= mi:
        mi = P[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
d = [0] + [float("inf")] * (n-1)
for i in range(1,n):
    for j in range(max(0,i-k),i):
        d[i]=min(d[i],d[j] + abs(h[i]-h[j]))
print(d[-1])

### FIXED CODE ###

n , k = map(int,input().split())
h = list(map(int,input().split()))
import numpy as np
h = np.array(h)
dp =np.zeros(n,dtype = int)
for i in range(1,n):
    s = max(0,i-k)
    dp[i] = np.min(dp[s:i] + np.abs(h[s:i] - h[i]))
print(dp[-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(s: str, K: int):

    index_dict = {}
    for i in range(len(s)):
        if index_dict.get(s[i]) == None:
            index_dict[s[i]] = [i]
        else:
            index_dict[s[i]].append(i)

    value_list = sorted(set(list(s)))
    candidate = set()
    for string in value_list:
        index = index_dict[string]
        for i in index:
            tmp_s = ""
            for j in range(i,len(s)):
                tmp_s += s[j]
                candidate.add(tmp_s)
        if len(candidate) >= K:
            break
    candidate = list(candidate)
    candidate.sort()
    print(candidate[K-1])

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    solve(s, K)

if __name__ == '__main__':
    main()


### FIXED CODE ###

s = input()
k = int(input())
substrings = []
index = []
for ss in sorted(list(set(s))):
  index_list = [n for n, v in enumerate(s) if v == ss]
  for i in index_list:##初期位置
    for j in range(1,min(k+1,len(s)-i+1)):##長さ
      substrings.append(s[i:i+j])
  if len(set(substrings)) >= k:
    break
print(sorted(list(set(substrings)))[k-1])
### BUGGY CODE ###

from fractions import gcd

MOD = 1000000000 + 7

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

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

l = 1
for i in A:
    l = lcm(l, i)

ans = 0
for i in A:
    ans += (l // i) % MOD
print(int(ans % MOD))


### FIXED CODE ###

from fractions import gcd

MOD = 1000000000 + 7

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

l = 1
ans = 0
for a in A:
    g = gcd(a, l)
    l = (l // g) * a
    ans = (ans * (a // g)) % MOD
    ans = (ans + (l // a)) % MOD
print(int(ans))
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for sum_w in range(W + 1):
            if sum_w - weight[i] >= 0:
                dp[i + 1][sum_w] = dp[i][sum_w - weight[i]] + value[i]
            if dp[i + 1][sum_w] < dp[i][sum_w]:
                dp[i + 1][sum_w] = dp[i][sum_w]

    print(dp[N][W])
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for sum_w in range(W + 1):
            if sum_w - weight[i] >= 0:
                dp[i + 1][sum_w] = dp[i][sum_w - weight[i]] + value[i]
            if dp[i + 1][sum_w] < dp[i][sum_w]:
                dp[i + 1][sum_w] = dp[i][sum_w]

    print(dp[N][W])
    return


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

N = int(input())
import math
a = math.factorial(N)

ans = 0
for i in range(1, a+1):
    if a%i == 0:
        ans += 1
print(ans%(10**9+7))

### FIXED CODE ###

import math
import collections

N = int(input())
a = math.factorial(N)
check = []
ans = 1
i = 2

while a != 1:
    if a % i == 0:
        a //= i
        check.append(i)
    else:
        i += 1
        
check = collections.Counter(check).values()
for i in check:
    ans *= (i+1)
    ans %= 10**9+7
print(ans)
### BUGGY CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    for _ in range(k):
        b=[0]*n
        for i,t in enumerate(a):
            if(j:=i-t)<0:j=0
            b[j]+=1
            if(j:=i-~t)<n:b[j]-=1
        a=list(accumulate(b))
        if min(a)==n:break
    print(' '.join(map(str,a)))
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

n,k = map(int,input().split())
h = sorted(list(map(int, [input() for i in range(n)])))
ans = int(max(h))

for j in range(n-k+1):
    ans = min(ans, (max(h[j:j+k])-min(h[j:j+k])))
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
### BUGGY CODE ###

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

p_temp = float("inf")

ans = N
for i in range(N):
	flag = 0
	for j in range(i):
		if p[j] <= p[i]:
			flag = 1
	ans -= flag
print(ans)

### FIXED CODE ###

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

p_min = [0]*N

p_min[0] = N+1
for i in range(1,N):
	p_min[i] = min(p[i-1],p_min[i-1])

ans = 0

for i in range(N):
	if p_min[i] >= p[i]:
		ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
count = 1
P = list(map(int,input().split()))
for n in range(1,N):
    if min(P[0:n]) >= P[n]:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
count = 1
P = list(map(int,input().split()))
last_min = P[0]
for n in range(1,N):
    if last_min >= P[n]:
        count += 1
    last_min = min(last_min,P[n])
print(count)
### BUGGY CODE ###

N = int(input())
S = list(input())
S_set = set()
i_set = set()

ans_list = {}


for i in range(N):
    if i in i_set:
        continue
    i_set.add(i)
    for j in range(i+1, N):
        if not S[j + 1:N] or S[i] + S[j] in S_set:
            continue
        ans_list[S[i] + S[j]] = S[j + 1:N]
        S_set.add(S[i] + S[j])
count = 0
# print(ans_list)
ans_len_list = [len(set(value)) for value in ans_list.values()]
print(sum(ans_len_list))

### FIXED CODE ###

N = int(input())
S = list(input())
visited = {}

count = 0

for i, s in enumerate(S):
    if s in visited:
        continue
    visited[s] = []
    for j, s2 in enumerate(S[i+1:N-1]):
        # print(s, s2, S[i + j + 2:N])
        if s2 in visited[s]:
            continue
        count += len(set(S[i + j + 2:N]))
        visited[s].append(s2)
        # print(s, s2, set(S[j + 1:N]))
print(count)
### BUGGY CODE ###

n = int(input())
ListP = [n+1] + [int(i) for i in input().split()] + [n+1]
#ListPos = [ListP.index(i) for i in range(1, n+1)]
points = 0
for i in (range(0, n-1)):
	countHigh1 = 0
	countHigh2 = 0
	countLow1 = 0
	countLow2 = 0
	j = k = ListP.index(i+1)
	#print(j)
	while(True):
		countHigh1 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		if (j == n+1):
			break
		countHigh2 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		countLow1 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	while(True):
		if (k == 0):
			break
		countLow2 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	points += (i+1) * (countLow1 * countHigh2 + countHigh1 * countLow2)
	#print(points, countLow1, countHigh2, countHigh1, countLow2)
print(points)

### FIXED CODE ###

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

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)
### BUGGY CODE ###

N=int(input())

d=[-1]*(N+1)
d[0]=0
d[1]=0

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

nlist=[]

def search(A,nlist):
	global d	
	t=[]
	for ne in nlist:
		for a,b,w in A:
			if a==ne and d[b]==-1:
				d[b]=d[a] if w%2==0 else (d[a]+1)%2
				t.append(b)
			if b==ne and d[a]==-1:
				d[a]=d[b] if w%2==0 else (d[b]+1)%2
				t.append(a)
	
	if t!=[]:
		search(A,t)

search(A,[1])
print(*d[1:],sep='\n')

### FIXED CODE ###

N=int(input())

graph=[[] for i in range(N+1)]

for i in range(N-1):
	a,b,w=map(int,input().split())
	graph[a].append([b,w])
	graph[b].append([a,w])


color=[-1]*(N+1)
color[1]=0

ne=[1]

while ne!=[]:
	t=ne.pop()
	for s,w in graph[t]:
		if color[s]==-1:
			ne.append(s)
			color[s]=color[t] if w%2==0 else (color[t]+1)%2

print(*color[1:],sep='\n')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


n, m = map(int, input().split())
path = list(list(map(int, input().split())) for _ in range(m))

dic = dict()
for i in range(m):
    p = path[i]
    if p[0] not in dic:
        dic[p[0]] = [p[1]]
    else:
        dic[p[0]].append(p[1])
    if p[1] not in dic:
        dic[p[1]] = [p[0]]
    else:
        dic[p[1]].append(p[0])
        
table = [0]*n
sign = [0]*n

def bfs(k):
    for i in dic[k]:
        if table[i-1] == 0 and i != 1:
            table[i-1] = table[k-1] + 1
            sign[i-1] = k
        elif table[k-1] + 1 < table[i-1]:
            table[i-1] = table[k-1] + 1
            sign[i-1] = k
        else:
            continue
        bfs(i)
    return

bfs(1)

print("Yes")
for i in range(n-1):
    print(sign[i+1])

### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
path = list(list(map(int, input().split())) for _ in range(m))

d = deque()

dic = dict()
for i in range(m):
    p = path[i]
    if p[0] not in dic:
        dic[p[0]] = [p[1]]
    else:
        dic[p[0]].append(p[1])
    if p[1] not in dic:
        dic[p[1]] = [p[0]]
    else:
        dic[p[1]].append(p[0])
        
sign = [0]*n
done = [0]*n
done[0] = 1

for i in dic[1]:
    d.appendleft(i)
    sign[i-1] = 1
    done[i-1] = 1

while len(d) > 0:
    x = d.pop()
    for i in dic[x]:
        if done[i-1] == 0:
            d.appendleft(i)
            sign[i-1] = x
            done[i-1] = 1
        
print("Yes")
for i in range(n-1):
    print(sign[i+1])
### BUGGY CODE ###

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


dic = {}
ans_dic = {}
for t in A:
    tmp = A.count(t)
    dic[t] = tmp
    ans_dic[t] = tmp * (tmp - 1) // 2
    
# print(dic)
# print(ans_dic)
ans = sum(ans_dic.values())
# print(ans)
for i in range(N):
    val = dic.get(A[i])
    print(ans-val+1)

### FIXED CODE ###

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

dic = {}
ans = 0
# for t in A:
#     if t in dic.keys():
#         continue
#     tmp = A.count(t)
#     dic[t] = tmp
#     ans += tmp*(tmp-1)//2

for a in A:
    tmp = dic.get(a)
    if tmp == None:
        dic[a] = 1
    else:
        dic[a] = tmp + 1

for key in list(dic.keys()):
    tmp = dic.get(key)
    ans += tmp * (tmp - 1) // 2
    

for a in A:
    val = dic.get(a)
    print(ans-val+1)
### BUGGY CODE ###

#C問題
import sys
sys.setrecursionlimit(500000)
N,M = map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
reach=[-1]*(N)
reach[0]=0
ans=0
def cdfs(n):
    global ans
    global reach
    if sum(reach)==0:
        ans+=1
        reach=[-1]*(N)
        reach[0]=0
        return
    else:
        for j in range(N):
            if reach[j] == -1 and ([n+1,j+1] in ab or [j+1,n+1] in ab):
                reach[j] = 0
                cdfs(j)
                reach[j] = -1
            else:
                pass
        return
reach[0]=0
cdfs(0)
print(ans)
    

### FIXED CODE ###

#C
import itertools
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]

path = [(i+1) for i in range(N)]
p_list = list(itertools.permutations(path,N))

ans = 0
for pl in p_list:
    if pl[0] == 1:
        flag = 0
        for i in range(N-1):
            ab1 = [pl[i],pl[i+1]]
            ab2 = [pl[i+1],pl[i]]
            if ab1 in AB or ab2 in AB:
                pass
            else:
                flag = 1
                break
        if flag == 0:
            ans+=1
            
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if (j-i)!=(k-j):
                if S[i]!=S[j] and S[j]!=S[k] and S[i]!=S[k]:
                    ans+=1
print(ans)


### FIXED CODE ###

N=int(input())
S=input()
r,g,b=0,0,0
for i in range(N):
    if S[i]=="R":
        r+=1
    elif S[i]=="G":
        g+=1
    elif S[i]=="B":
        b+=1
# j-i=k-j  2j-i-k=0 k=i-2j について調べるもしRGBなら、それをrgbからマイナスする
tmp=0
for i in range(N):
    for j in range(i+1,N):
        k=2*j-i
        if k<N and k>=0:
            if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
                tmp+=1
# print("rgb",r*g*b)
# print("tmp",tmp)
print(r*g*b-tmp)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[int]"):
    ans = 1
    for a in A:
        ans = ans * a

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


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[int]"):
    A.sort()
    ans =1
    for a in A:
        ans = ans * a

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


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[[0 for _ in range(C+2)] for _ in range(R+2)] for _ in range(4)]

for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[m][ni][nj] = max(dp[m][ni][nj], dp[m][i][j])
			if m < 3:
				dp[m+1][ni][nj] = max(dp[m+1][ni][nj], dp[m][i][j]+I[ni][nj])
			ni, nj = i+1, j
			dp[0][ni][nj] = max(dp[0][ni][nj], dp[m][i][j])
			dp[1][ni][nj] = max(dp[1][ni][nj], dp[m][i][j]+I[ni][nj])
ans = 0
for m in range(4):
	ans = max(ans, dp[m][R][C])
print(ans)


### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)
### BUGGY CODE ###

# D - RGB Triplets
def main():
    _ = int(input())
    S = input().rstrip()
    cnt = 0
    for j, b in enumerate(S[1:-1], 1):
        for i, a in enumerate(S[:j]):
            for k, c in enumerate(S[j + 1 :], j + 1):
                if a == b or a == c or b == c:
                    continue
                elif j - i == k - j:
                    continue
                cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# D - RGB Triplets
from collections import defaultdict


def main():
    _ = int(input())
    S = input().rstrip()
    indices = defaultdict(set)
    for i, c in enumerate(S):
        indices[c].add(i)
    cnt = len(indices["R"]) * len(indices["G"]) * len(indices["B"])
    for c1, c2, c3 in ["RGB", "GBR", "BRG"]:
        cnt -= sum(
            (i + j) % 2 == 0 and (i + j) // 2 in indices[c3]
            for i in indices[c1]
            for j in indices[c2]
        )
    print(cnt)


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

n = int(input())
a = list(map(int, input().split()))
allxor = 0
for i in range(n):
    allxor = allxor^a[i]
ans = ''
for i in range(n):
    ans= ans +str(allxor^a[i])+' '
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
allxor = 0
ans = [0]*n
for i in range(n):
    allxor = allxor^a[i]
for i in range(n):
    ans[i] = allxor^a[i]
ansstr = " ".join(map(str,ans))
print(ansstr)
### BUGGY CODE ###

from collections import deque
import copy

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = deque()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.append([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while q:
        x,y = q.popleft()
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)


### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = deque()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.append([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while q:
        x,y = q.popleft()
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)
"""))
### BUGGY CODE ###

N,M = input().split()
N = int(N)
M = int(M)
price_list = input().split()
for i in range(N):
  price_list[i] = int(price_list[i])

for m in range(M):
  max_num = price_list.index(max(price_list))
  price_list[max_num] = int(price_list[max_num] / 2)
print(sum(price_list))

### FIXED CODE ###

import heapq

N,M = input().split()
N = int(N)
M = int(M)
price_list = input().split()
 
heap_list = []
for i in price_list:
  heapq.heappush(heap_list, int(i) * (-1))

for _ in range(M):
  max_num = heapq.heappop(heap_list)
  heapq.heappush(heap_list, int(max_num /2))
  
print(sum(heap_list) * (-1))
### BUGGY CODE ###

n,a,b,c,d=map(int,input().split())

mod=10**9+7
fac=[1]*(n+3)
finv=[1]*(n+3)

t=1
for i in range(1,n+3):
    t*=i
    t%=mod
    fac[i]=t

t=1
for i in range(1,n+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    finv[i]=t

def comb(a,b):
    if a<b:return 0
    return fac[a]*(finv[a-b]*finv[b]%mod)%mod

dp=[[0 if i else 1 for i in range(n+2)] for _ in range(n+2)]

for i in range(a,b+1):
    for j in range(n+1):
        if not dp[i][j]:continue
        if j:dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
        p=1
        for k in range(1,1+(n-j)//i):
            if not k<=d:break
            p=((p*comb(n-j-i*(k-1),i)%mod)*pow(k,mod-2,mod))%mod

            if k>=c:
                dp[i+1][j+i*k]+=(dp[i][j]*p%mod)
                dp[i+1][j+i*k]%=mod

print(dp[b+1][n]%mod)


### FIXED CODE ###

from functools import lru_cache
n,a,b,c,d=map(int,input().split())

mod=10**9+7
fac=[1]*(n+3)
finv=[1]*(n+3)

t=1
for i in range(1,n+1):
    t*=i
    t%=mod
    fac[i]=t
t=1
for i in range(1,n+1):
    t*=pow(i,mod-2,mod)
    t%=mod
    finv[i]=t

finvp = [finv]
for i in range(n-1):
    p=finvp[-1]
    q=[p[i]*finv[i]%mod for i in range(n+1)]
    finvp.append(q)

dp = [[0 for _ in range(n+1)] for _ in range(b+1)]
dp[a-1][0] = 1

for i in range(a-1,b):
    for j in range(n+1):
        dp[i+1][j]=dp[i][j]
        for k in range(c,1+min(d,j//(i+1))):
            x=j-k*(i+1)
            dp[i+1][j]+=fac[j]*finv[x]*finvp[k-1][i+1]*finv[k]*dp[i][x]%mod
        dp[i+1][j]%=mod
print(dp[b][n])