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

N = int(input())
S = input()

# 左は尺取り。しかも３とって失敗したら、l,r双方いんくりしてよい
# 右は総当たり。

ans = 0
l,r = 0,1
while l<N and r<N:
  findf = False
  target = S[l:r]
  L = r-l
  for k in range(l+L,N-1):
    compare = S[k:k+L]
    #print(target, compare)
    if target == S[k:k+L]:
      ans = max(ans,L)
      findf = True
      break
  if findf and r < N-1:
    r += 1
  else:
    l += 1
    r = min(r+1,N-1)
    
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

# 左は尺取り。しかも３とって失敗したら、l,r双方いんくりしてよい
# 右は総当たり。

ans = 0
l,r = 0,1
while l<N and r<N:
  findf = False
  target = S[l:r]
  L = r-l
  for k in range(l+L,N-1):
    compare = S[k:k+L]
    #print(target, compare)
    if target == S[k:k+L]:
      ans = max(ans,L)
      findf = True
      break
  if findf and r < N-1:
    r += 1
  else:
    l += 1
    r = min(r+1,N-1)
    
print(ans)
### BUGGY CODE ###

import heapq
def dijkstra(s, type=0):
    dist = [float('inf')] * N
    dist[s] = 0
    que = [(0, s)]
    heapq.heapify(que)
    while que:
        d, v = heapq.heappop(que)
        if d > dist[v]:
            continue
        for u, a, b in E[v]:
            if type != 0:
                a, b = b, a
            tmp_d = d + a
            if tmp_d < dist[u]:
                dist[u] = tmp_d
                heapq.heappush(que, (tmp_d, u))
    return dist

N, M, s, t = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    E[u-1].append((v-1, a, b))
    E[v-1].append((u-1, a, b))

dist_s = dijkstra(s-1)
dist_t = dijkstra(t-1, 1)
ans = float('inf')
idx = -1
for i in range(N):
    if idx >= i:
        print(10 ** 15 - ans)
        continue
    tmp = float('inf')
    for j in range(i, N):
        if dist_s[j] + dist_t[j] <= tmp:
            tmp = dist_s[j] + dist_t[j]
            ans = tmp
            idx = j
    print(10 ** 15 - ans)


### FIXED CODE ###

import heapq
def dijkstra(s, neighbor):
    dist = [float('inf')] * N
    dist[s] = 0
    que = [(0, s)]
    heapq.heapify(que)
    while que:
        d, v = heapq.heappop(que)
        if d > dist[v]:
            continue
        for u, l in neighbor[v]:
            tmp_d = d + l
            if tmp_d < dist[u]:
                dist[u] = tmp_d
                heapq.heappush(que, (tmp_d, u))
    return dist

N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    yen[u-1].append((v-1, a))
    yen[v-1].append((u-1, a))
    snuuk[u-1].append((v-1, b))
    snuuk[v-1].append((u-1, b))

dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
    if dist_s[i] + dist_t[i] < tmp:
        tmp = dist_s[i] + dist_t[i]
    ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import Counter
from itertools import combinations

N = int(input())
s = [str(input()) for x in range(N)]

cs = [Counter(x) for x in s]
ccs = combinations(cs, 2)

ans = 0
for i in ccs:
    if i[0]==i[1]:
        ans +=1

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter
from itertools import combinations

N = int(input())
c = ["".join(sorted(str(input()))) for x in range(N)]
cs = Counter(c)

ans=0
for i in cs.values():
    if i!=1:
        ans += (i * (i-1))/2

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

# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    # The dict of networks as sets. Keys are leaders.
    networks = [None] * n
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        network = set()
        network_add = network.add
        stack = [person]
        stack_append = stack.append
        stack_pop = stack.pop
        while stack:
            new = stack_pop()
            visited[new] = True
            net_leaders[new] = person
            network_add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack_append(adj)
        networks[person] = network

    answers = []
    answers_append = answers.append
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers_append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        network = set()
        network_add = network.add
        stack = [person]
        stack_append = stack.append
        stack_pop = stack.pop
        while stack:
            new = stack_pop()
            visited[new] = True
            net_leaders[new] = person
            network_add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack_append(adj)
        networks[person] = network

    answers = []
    answers_append = answers.append
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers_append(ans)

    print(*answers)
    return


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

n=int(input())
a=list(map(int,input().split()))
count=1
for i in range(n):
    if a[i]==0:
        print(0)
        exit()
    count=count*a[i]
if count>10**18:
    print(-1)
else:
    print(count)

### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
ans = 1
if 0 in lis:
  print(0)
  exit()
for num in lis:
  ans *= num
  if ans > 10 ** 18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

S = str(input())

def solution(S):
    a = len(S)
    b = list(0 for j in range(4, a+1)
        for i in range(a-j+1)
            if int(S[i:i+j])%2019==0)
    print(len(b))
solution(S)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

from heapq import heappop, heappush

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

l = []
for _ in range(H):
    s = input()
    l.append([1 if i=="#" else 0 for i in s])

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

q = [(0, Ch, Cw)]
used = [[False]*W for _ in range(H)]
used[Ch][Cw] = True

while q:
    cost, h, w = heappop(q)
    if h==Dh and w==Dw:
        break

    for hh, ww in [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]:
        if not (0<=hh<H and 0<=ww<W):
            continue
        if l[hh][ww] or used[hh][ww]:
            continue
        used[hh][ww] = True
        heappush(q, (cost, hh, ww))

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if dh==0 and dw==0:
                continue
            hh = h+dh
            ww = w+dw
            if not (0<=hh<H and 0<=ww<W):
                continue
            if l[hh][ww]:
                continue
            heappush(q, (cost+1, hh, ww))


if h==Dh and w==Dw:
    print(cost)
else:
    print(-1)


### FIXED CODE ###

from heapq import heappop, heappush
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = []
    for _ in range(H):
        s = input()
        l.append([1 if i=="#" else 0 for i in s])

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    q = [(0, (Ch, Cw))]
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch][Cw] = 0

    while q:
        cost, pos = heappop(q)
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = h+dh
                ww = w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if (abs(dh)==1 and abs(dw)==0) or (abs(dh)==0 and abs(dw)==1):
                    if costs[hh][ww] > costs[h][w]:
                        costs[hh][ww] = costs[h][w]
                        heappush(q, (cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    heappush(q, (cost+1, (hh, ww)))

    print(costs[Dh][Dw] if costs[Dh][Dw]!=INF else -1)


solve()
### BUGGY CODE ###

N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
value=0
mod=10**9 + 7
if K==1:
    print(0)
    exit()
z=1
for i in range(N):
    if i>=K-1:
        value+=z*A[i]
        value-=z*A[N-1-i]
        z*=i-(K-1) + K
        z//=i-(K-1) + 1
    value%=mod
print(value)


### FIXED CODE ###

mod = 10**9 + 7
kaijotable = [0 for i in range(200100)]
kaijotable[0] = 1
for i in range(1, 200051):
    kaijotable[i] = (kaijotable[i - 1] * i) % mod

def doubling(x, y, mod):
    if y == 0:
        return 1
    if y == 1:
        return x
    elif y % 2 == 0:
        val = (doubling(x, y // 2, mod) ** 2) % mod
        return val
    else:
        val = (doubling(x, y // 2, mod) ** 2) * x % mod
        return val

def gyaku(x):
    gyaku = doubling(x, mod - 2, mod) % mod
    return gyaku

gyakutable = [0 for i in range(200100)]
gyakutable[200050] = gyaku(kaijotable[200050])
for i in range(200050, 0, -1):
    gyakutable[i - 1] = i * gyakutable[i] % mod

N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
value=0
mod=10**9 + 7
if K==1:
    print(0)
    exit()

z=0

for i in range(N):
    if i>=K-1:
        c=kaijotable[z+K-1] * gyakutable[K-1] * gyakutable[z+K-1-(K-1)] % mod
        value+=c*A[i]
        value-=c*A[N-1-i]

        z+=1
    value%=mod
print(value)
### BUGGY CODE ###

n,q = map(int, input().split())
s = str(input())
lr = [list(map(int, input().split())) for _ in range(q)]
ans = [0]*q
i = 0
while i<n-1:

    if s[i]=="A" and s[i+1]=="C":
        for j in range(q):
            if lr[j][0]-1<=i and lr[j][1]-2>=i:
                ans[j] = ans[j]+1
            else:
                continue
        i +=2
    elif s[i+1]=="A":
        i+=1
    else:
        i +=2

for i in range(q):
    print(ans[i])

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
t = [0]*(n+1)
for i in range(n):
    if s[i:i+2]=="AC":
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]

for i in range(q):
    l,r = map(int, input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())

total = 0
for m in range(1,N):
    sub = 1

    tmp = m
    for i in range(2, int(-(-m**0.5//1))+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            sub *= (cnt + 1)

    if tmp != 1:
        sub *= 2

    total += sub

print(total)



### FIXED CODE ###

import sys
import math

input = sys.stdin.readline

N = int(input())

total = 0
for i in range(1, N):
    total += (N-1) // i

print(total)
### BUGGY CODE ###

N=int(input())

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

for i in range(N):
  A=X.copy()
  A.pop(i)
  A.sort(reverse=True)
  print(A[int(N/2)-1])

### FIXED CODE ###

N=int(input())

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

A=X.copy()
A.sort(reverse=True)

left=A[int(N/2)-1]
right=A[int(N/2)]

for i in range(N):
  if X[i]>=left:
    print(right)
  else:
    print(left)
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N,M=list(map(int,input().split()))
road = [0]*(N-1)
for _ in range(M):
    l,r=map(int,input().split())
    for i in range(l-1,r-1):
        road[i]+=1
if sum(road)%2==0:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N,M=list(map(int,input().split()))
road = [0]*(N)
for _ in range(M):
    l,r=map(int,input().split())
    road[l-1]+=1
    road[r-1]-=1
road = list(itertools.accumulate(road))[:-1]

flag=0
for ro in road:
    if ro%2==1:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

#coding=UTF-8


mozir=input()
hyo=mozir.split(' ')

N=int(hyo[0])
M=int(hyo[1])

A=[]
B=[]
Cost=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A.append(int(hyo[0])-1)
    B.append(int(hyo[1])-1)
    Cost.append(int(hyo[2]))
    
#先ず得点が正になるループを探す
eipap=False
for idx in range(0,N,1):
    tansaku=[(idx,0)]
    while len(tansaku) > 0:
        next_tansaku=[]
        for mono in tansaku:
            for idy in range(0,M,1):
                if A[idy]==mono[0]:
                    next_tansaku.append((B[idy],mono[1]+Cost[idy]))

        ##remove less hopeful thing
        tmp_tan=sorted(next_tansaku,key=lambda po:po[1])
        kirei_next_tan=sorted(tmp_tan,key=lambda po:po[0])
        #print(kirei_next_tan)
        
        for tenn in kirei_next_tan:
            if tenn[0]==idx and tenn[1]>0:
                eipap=True
                break

        if eipap:
            break
        else:
            tansaku=kirei_next_tan

if eipap:
    print('inf')
else:
    #無ければ、普通の経路探索のようなことをする
    tmp_score=[None]*N #マイナス点のときもある
    tmp_score[0]=0
    tansaku=[0]
    while len(tansaku) > 0:
        next_tansaku=[]
        for mono in tansaku:
            for idy in range(0,M,1):
                if A[idy]==mono:
                    kouho_ten=tmp_score[mono]+Cost[idy]
                    if tmp_score[B[idy]] == None or kouho_ten > tmp_score[B[idy]]:
                        tmp_score[B[idy]]=kouho_ten
                        next_tansaku.append(B[idy])

        tansaku=next_tansaku

    print(tmp_score[N-1])


### FIXED CODE ###

#coding=UTF-8

#ゴールに関係無い袋小路で永パされると、探索が収束しない
#かつ答えがinfでないということで 修正

#表にあるかを尋ねるのが重いので
#データ構造を変えて回避する
mozir=input()
hyo=mozir.split(' ')

N=int(hyo[0])
M=int(hyo[1])

#idx番目の都市に繋っている道とコストのタプルを持つリスト
tuuro=[]
# [] はコピーがしんどいものだったりするので
# 参照でごまかしたりしてくる
# なので1個づつ書いている
for idx in range(0,N,1):
    tuuro.append([])


A=[]
B=[]

for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    tuuro[int(hyo[0])-1].append((int(hyo[1])-1,int(hyo[2])))

#print(tuuro)
#普通の経路探索のようなことをする
#永パ
tmp_score=[None]*N #マイナス点のときもある
tmp_score[0]=0
tansaku=[0]
loopconut=0
while len(tansaku) > 0:
    loopconut=loopconut+1
    next_tansaku=[]
    for mono in tansaku:
        for deru in tuuro[mono]:
            kouho_ten=tmp_score[mono]+deru[1]
            if tmp_score[deru[0]] == None or kouho_ten > tmp_score[deru[0]]:
                tmp_score[deru[0]]=kouho_ten
                next_tansaku.append(deru[0])

    tansaku=list(set(next_tansaku))
    if loopconut==N-1:
        tmp_ans=tmp_score[N-1] #cannot be None
    elif loopconut==2*N-1:
        #period must be eqal or less than N
        if tmp_score[N-1] > tmp_ans:
            print('inf')
            break
        else:
            #関係の無い無限ループ
            print(tmp_score[N-1])
            break
else:
    print(tmp_score[N-1])
### BUGGY CODE ###

import networkx as nx
N, M = map(int, input().split())

G = nx.Graph()
G.add_nodes_from(range(1, N+1))
for _ in range(M):
  a, b = map(int, input().split())
  G.add_edge(a, b)

dist = nx.shortest_path_length(G, target=1)
print('Yes')
for i in range(2, N+1):
  print(min((dist[j], j) for j in nx.all_neighbors(G, i))[1])
    





### FIXED CODE ###

import networkx as nx
N, M = map(int, input().split())

G = nx.Graph()

G.add_edges_from(tuple(map(int, input().split())) for _ in range(M))

dist = nx.shortest_path_length(G, target=1)
print('Yes')
for i in range(2, N+1):
  print(min((dist[j], j) for j in nx.all_neighbors(G, i))[1])
### BUGGY CODE ###

n,k,q=map(int,input().split())
as_=[int(input()) for _ in range(q)]
for p in range(n):
    if k-q+as_.count(p+1)>0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
as_=[int(input()) for _ in range(q)]
ps=[k-q]*n
for a in as_:
    ps[a-1]+=1
for p in ps:
    print('Yes'if p>0 else 'No')
### BUGGY CODE ###

import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,m= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
b = []
for i in range(m):
    x,y = (int(i) for i in input().split())
    b.append([y,x])
b.sort(reverse=True)
a.sort()
s = 0
while (len(a)):
    if a[0] < b[0][0]:
        a.pop(0)
        s+=b[0][0]
        b[0][1]-=1
        if b[0][1] == 0:
            b.pop(0)
            if b == []:
                s += sum(a)
                break
    else:
        b.pop(0)
        if b == []:
            s+=sum(a)
            break
print(s)

### FIXED CODE ###

import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,m= (int(i) for i in input().split())       #入力整数横2つ以上
a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
b = []
for i in range(m):
    x,y = (int(i) for i in input().split())
    b.append([y,x])
b.sort(reverse=True)
a.sort()
s = 0
pa = 0
pb = 0
while (pa < len(a)):
    if a[pa] < b[pb][0]:
        pa+=1
        s+=b[pb][0]
        b[pb][1]-=1
        if b[pb][1] == 0:
            pb+=1
            if len(b) == pb:
                s += sum(a[pa:])
                break
    else:
        pb+=1
        if len(b) == pb:
            s+=sum(a[pa:])
            break
print(s)
### BUGGY CODE ###

s = input()
while(s != s.replace("ST", "", 1)):
    s = s.replace("ST", "", 1)
print(len(s))

### FIXED CODE ###

s = input()
cnt = 0
t = 0
for c in s:
    if(c == "S"):
        cnt += 1
    else: # T
        if(cnt > 0):
            cnt -= 1
        else:
            t += 1
print(cnt + t)
### BUGGY CODE ###

from collections import deque

def cal():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = deque()
    INF = float('inf')
    counts = [[INF]*w for _ in range(h)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.append([i, j])
                counts[j][i] = 0

    while q:
        x, y = q.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if a[y0][x0] == '.' and counts[y][x]+1 < counts[y0][x0]:
                    a[y0][x0] = '#'
                    counts[y0][x0] = counts[y][x]+1
                    q.append([x0, y0])
    ans = 0
    for i in counts:
        ans = max(ans, max(i))
    print(ans)

cal()


### FIXED CODE ###

from collections import deque

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False]*w+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()    
        if not counts[x+1][y]:
            counts[x+1][y] = True
            q.append([x+1, y, z+1])
        if not counts[x-1][y]:
            counts[x-1][y] = True
            q.append([x-1, y, z+1])
        if not counts[x][y+1]:
            counts[x][y+1] = True
            q.append([x, y+1, z+1])
        if not counts[x][y-1]:
            counts[x][y-1] = True
            q.append([x, y-1, z+1])
    print(z)
    

cal()
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(n for n in range(N+1))
ans = 0
for i in range(K,N+2):
  L = sum(A[:i])
  R = sum(A[N-i+1:N+1])
  ans += (R-L+1)
print(ans%((10**9)+7))

### FIXED CODE ###

N, K = map(int, input().split())
A = list(n for n in range(N+1))
ans = 0
for i in range(K,N+2):
  L = i*(i-1)//2
  R = i*(2*N+1-i)//2
  ans += (R-L+1)
print(ans%((10**9)+7))