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

MOD = 10**9 + 7  # 出力の制限

r1, c1, r2, c2 = list(map(int, input().split()))


# https://qiita.cmb/derodero24/items/91b6468e66923a87f39f
def cmb(n, r):
  if (r < 0 or r > n):
    return 0
  r = min(r, n - r)
  return g1[n] * g2[r] * g2[n - r] % MOD


N = 10**7
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
  g1.append((g1[-1] * i) % MOD)
  inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
  g2.append((g2[-1] * inverse[-1]) % MOD)

print(cmb(c1 + r1, r1) - cmb(1 + c2 + r1, r1) -
      cmb(1 + c1 + r2, 1 + r2) + cmb(2 + c2 + r2, 1 + r2))


### FIXED CODE ###

MOD = 10**9 + 7  # 出力の制限

r1, c1, r2, c2 = list(map(int, input().split()))


# https://qiita.cmb/derodero24/items/91b6468e66923a87f39f
def cmb(n, r):
  if (r < 0 or r > n):
    return 0
  r = min(r, n - r)
  return g1[n] * g2[r] * g2[n - r] % MOD


N = 2 * 10**6 + 3
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
  g1.append((g1[-1] * i) % MOD)
  inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
  g2.append((g2[-1] * inverse[-1]) % MOD)

# Sum[Sum[Binomial[i + j, i], {i, r1, r2}], {j, c1, c2}]
# Binomial[c1 + r1, r1] - Binomial[1 + c2 + r1, r1] -  Binomial[1 + c1 + r2, 1 + r2] + Binomial[2 + c2 + r2, 1 + r2]

print((cmb(c1 + r1, r1) - cmb(1 + c2 + r1, r1) -
       cmb(1 + c1 + r2, 1 + r2) + cmb(2 + c2 + r2, 1 + r2)) % MOD)
### BUGGY CODE ###

from math import sqrt
import heapq

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    st = set()
    for i in range(n):
        st.add(i)
    dist = [float("inf")]*n
    dist[n-2] = 0
    dist[n-1] = calc(arr, n-2, n-1)
    hq = []
    heapq.heappush(hq, [0, n-2])
    while len(hq) > 0:
        _, p = heapq.heappop(hq)
        if p in st:
            st.remove(p)
            for nxt in st:
                d = calc(arr, p, nxt)
                if dist[nxt] > dist[p] + d:
                    dist[nxt] = dist[p] + d
                    heapq.heappush(hq, [dist[nxt], nxt])
    print(dist[-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

num_dict = dict()
for i in a:
    if i in num_dict.keys():
        num_dict[i] += 1
    else:
        num_dict[i] = 1

for i in range(q):
    ans = 0
    if b[i] in num_dict:
        if c[i] in num_dict:
            num_dict[c[i]] += num_dict.pop(b[i])
        else:
            num_dict[c[i]] = num_dict.pop(b[i])
    for k, v in num_dict.items():
        ans += k*v
    print(ans)

### FIXED CODE ###

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

num_dict = dict()
for i in a:
    if i in num_dict.keys():
        num_dict[i] += 1
    else:
        num_dict[i] = 1

ans = 0       
for k, v in num_dict.items():
  ans += k*v
 
for i in range(q):
    if b[i] in num_dict:
        if c[i] in num_dict:
            ans += (c[i] - b[i]) * num_dict[b[i]]
            num_dict[c[i]] += num_dict.pop(b[i])
        else:
            ans += (c[i] - b[i]) * num_dict[b[i]]
            num_dict[c[i]] = num_dict.pop(b[i])
    #print(num_dict)
    print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8

def check_merge(merged,S):
    merged = set(merged)
    for i in merged:
        for j, e in enumerate(S[i]):
            if int(e) and j in merged:
                return False
    return True

def run():
    N = int(sysread())
    S = []
    for i in range(N):
        S.append(input())

    ans = 0

    #for s in S:
    #    print(s)
    for k in range(N):
        #print(k, '-------------------')
        seen = set()
        seen.add(k)
        merged = [k]
        count = 0
        while merged:
            #print(merged)
            count += 1
            nexts = []
            for i in merged:
                for j, e in enumerate(S[i]):
                    if int(e) and not j in seen:
                        nexts.append(j)
                        seen.add(j)
            if not check_merge(merged, S):
                seen = set()
                break
            merged = nexts
        if len(seen) == N:
            ans = max(ans, count)
    if ans:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    run()


### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8

def check_merge(merged,S):
    merged = set(merged)
    for i in merged:
        for j, e in enumerate(S[i]):
            if int(e) and j in merged:
                return False
    return True

def run():
    N = int(sysread())
    S = []
    for i in range(N):
        S.append(input())

    ans = 0

    #for s in S:
    #    print(s)
    for k in range(N):
        #print(k, '-------------------')
        seen = set()
        seen.add(k)
        merged = [k]
        count = 0
        while merged:
            #print(merged)
            count += 1
            nexts = []
            for i in merged:
                for j, e in enumerate(S[i]):
                    if int(e) and not j in seen:
                        nexts.append(j)
                        seen.add(j)
            if not check_merge(merged, S):
                seen = set()
                break
            merged = nexts
        if len(seen) == N:
            ans = max(ans, count)
    if ans:
        print(ans)
    else:
        print(-1)


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

n = int(raw_input())
G = [[-1] * n] * n
d = [0] * n
 
for i in range(n):
    v = map(int, raw_input().split())
    for j in range(v[1]):
        G[v[0]][v[2+2*j]] = int(v[3+2*j])
 
flag = [0] * n
tn = [1]
r = 0
while True:
    for i in range(n):
        if flag[i] == 0 and i in tn:
            flag[i] = 1
            d[i] = r
            for j in range(n):
                if G[i][j] != -1 and flag[j] == 0:
                    tn.append(j)
    if len(tn) == n:
        break
    r += 1
 
for i in range(1, n+1):
    print(str(i) + " " + str(d[i]))

### FIXED CODE ###

n = int(input())
G = [[-1 for i in range(n)] for j in range(n)]
d = [999999 for i in range(n)]
  
for i in range(n):
    v = input().split()
    for j in range(int(v[1])):
        G[int(v[0])][int(v[2+2*j])] = int(v[3+2*j])

flag = [0] * n
tn = [0]
d[0] = 0
for k in range(n):
    for i in range(n):
        if i in tn:
            for j in range(n):
                if G[i][j] != -1:
                    if d[j] > d[i] + G[i][j]:
                        d[j] = d[i] + G[i][j]
                    if j not in tn:
                        tn.append(j)
  
for i in range(n):
    print(str(i) + " " + str(d[i]))
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]

direction = [[0,1],[0,-1],[1,0],[-1,0]]
black = np.zeros((H,W))
que = []
for i in range(H):
  for j in range(W):
    if G[i][j] == '#':
      que.append([i,j])
      black[i][j] = 0

while que:
  nh, nw = que.pop(0)
  for dh, dw in direction:
    if nh+dh<0 or nh+dh>H-1 or nw+dw<0 or nw+dw>W-1:
      continue
    if black[nh+dh][nw+dw] > 0:
      continue
    que.append([nh+dh,nw+dw])
    black[nh+dh][nw+dw] = black[nh][nw]+1
print(int(np.max(black)))

### FIXED CODE ###

import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['#' == x for x in input()] for _ in range(H)]
 
  black = deque([(i, j) for i in range(H) for j in range(W) if G[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not G[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not G[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not G[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not G[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

if (X + Y) % 3 != 0:
    print(0)
else:
    n = (2 * Y - X) / 3
    m = Y - 2 * n
    if n < 0 or m < 0:
        print(0)
        exit()
    total = math.factorial(n + m)
    n = math.factorial(n)
    m = math.factorial(m)
    total //= n
    total //= m
    # print(total)
    # print(nm)
    # tmp = total/nm
    print(total%mod)


### FIXED CODE ###

import math
tmp = input().split()
X = int(tmp[0])
Y = int(tmp[1])

mod = 10 ** 9 + 7

if (X + Y) % 3 != 0:
    print(0)
else:
    n = int((2 * Y - X) / 3)
    m = int(Y - 2 * n)
    if n < 0 or m < 0:
        print(0)
        exit()
    n %= mod
    m %= mod

    r = n
    n = n+m
    # if n - r < r:
    #     r = n - r
    # if r == 0:
    #     return 1
    # if r == 1:
    #     return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    # return result
    print(result % mod)
### BUGGY CODE ###

from numba import njit
N = int(input())
S = input()

R = S.count('R')
G = S.count('G')
B = S.count('B')

@njit
def f(S, N):
    tmp = 0
    for i in range(N):
        for j in range(i+1, N):
            k = j + (j - i)
            if k >= N:
                break
            if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
                tmp-=1
    return tmp
                
print(f(S,N) + R*G*B)

### FIXED CODE ###

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

R = S.count('R')
G = S.count('G')
B = S.count('B')
tmp = 0
for i in range(N):
    for j in range(i+1, N):
        k = j + (j - i)
        if k >= N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            tmp-=1
print(tmp + R*G*B)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N = II()

    if N == 1:
        print(0)
        return
    else:
        print(sum(range(N)))
        return

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N = II()

    if N == 1:
        print(0)
        return
    else:
        print(sum(range(N)))
        return

main()
### BUGGY CODE ###

n = int(input())
anstmp = ["a"]
cnt = 0
for i in anstmp:
  t = ord(i[-1])-95
  if cnt > 1000000:
    break
  for j in range(1,t+1):
    anstmp.append(i+chr(j+96))
  cnt += 1
ans = set()
for i in anstmp:
  if len(i) == n:
    ans.add(i)
ans = list(ans)
ans.sort()
print(*ans,sep="\n")

### FIXED CODE ###

n = int(input())
anstmp = ["a"]
cnt = 0
for i in anstmp:
  t = max(ord(k) for k in i)-95
  if cnt > 100000:
    break
  for j in range(1,t+1):
    anstmp.append(i+chr(j+96))
  cnt += 1
ans = set()
for i in anstmp:
  if len(i) == n:
    ans.add(i)
ans = list(ans)
ans.sort()
print(*ans,sep="\n")
### BUGGY CODE ###

s=input()

counter=[0]*2019
counter[0]=1
prefer=0
for i in range(len(s)):
    prefer=(prefer+10**i*int(s[-(i+1)]))%2019
    counter[prefer]+=1

ans=0
for i in range(2019):
    c=counter[i]
    ans+=c*(c-1)/2
print(int(ans))





### FIXED CODE ###

s=input()

counter=[0]*2019
counter[0]=1
num=0
t=1
prefer=0
for i in reversed(s):
    num+=int(i)*t
    num%=2019
    t*=10
    t%=2019
    counter[num]+=1

ans=0
for i in range(2019):
    c=counter[i]
    ans+=c*(c-1)/2
print(int(ans))
### BUGGY CODE ###

a, b = input().split()
a, b = int(a), int(b)

n = 1
for i in range(a, b + 1):
    n *= i

if n > 0:
    print("Positive")
elif n < 0:
    print("Negative")
else:
    print("Zero")


### FIXED CODE ###

a, b = input().split()
a, b = int(a), int(b)

if a < 0 < b:
    print("Zero")
elif 0 < a < b:
    print("Positive")
elif a < b < 0:
    if (b - a + 1) % 2 == 0:
        print("Positive")
    else:
        print("Negative")
### BUGGY CODE ###

n = int(input())

s = input()

dp = [[0 for i in range(n+1)] for j in range(n+1)]

for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
            
ans = 0

for i in range(n):
    for j in range(n):
        ans = max(ans,min(dp[i][j],j-i))
        
print(ans)

### FIXED CODE ###

n = int(input())

s = input()

dp = [[0 for i in range(n+1)] for j in range(n+1)]

for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
            
ans = 0

for i in range(n):
    for j in range(n):
        ans = max(ans,min(dp[i][j],j-i))
        
print(ans)
### BUGGY CODE ###

S = input()[::-1]

dp = [[0]*13]
MOD = 10**9+7

for i in range(1,len(S)+1):
  s = S[i-1]
  dp += [[0]*13]
  if s=='?':
    if i==1:
      for j in range(10):
        dp[i][j] = 1
    else:
      for j in range(13):
        for h in range(10):
          x = h*(10**(i-1))%13
          dp[i][j] += dp[i-1][(j-x)%13]
        dp[i][j] = dp[i][j]%MOD
  else:
    c = int(s)
    x = c*(10**(i-1))%13
    if i==1:
      dp[i][c]=1
    else:
      for j in range(13):
        dp[i][j] = dp[i-1][(j-x)%13]
print(dp[-1][5])

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            i = (_r + r) % 13
            tdp[i] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

def calc_exp(p):
    result = 0
    for n in p:
        result += expectation(n)
    return result


def expectation(p):
    n = sum(p)
    return 0.5 * n + 0.5 * len(p)


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    max_num = 0
    max_idx = -1
    for i in range(n-k+1):
        num = sum(p[i:i+k])
        if num >= max_num:
            max_num = num
            max_idx = i
    print(expectation(p[max_idx:max_idx+k]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def expectation(p):
    return 0.5 * sum(p) + 0.5 * len(p)


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    max_num = sum(p[0:k])
    max_idx = 0
    lst = [max_num]
    for i in range(1, n-k+1):
        num = lst[i-1] + p[i+k-1] - p[i-1]
        lst.append(num)

        if num >= max_num:
            max_num = num
            max_idx = i
    print(expectation(p[max_idx:max_idx+k]))


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

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    tree = [[] for _ in range(n)]
    for idx, a in enumerate(A):
        tree[a - 1].append(idx)
        tree[idx].append(a - 1)

    start = []
    depth = [0 for _ in range(n)]

    def dfs(v, p, d):
        depth[v] = d
        for u in tree[v]:
            if u == p:
                continue

            if visited[u]:
                start.append([u + 1, depth[u]])
                return
            else:
                visited[u] = True
                dfs(u, v, d + 1)
        return

    visited = [False for _ in range(n)]
    visited[0] = True
    dfs(0, -1, 0)
    
    for i in range(n):
        if i + 1 not in set(A):
            depth[i] = 0

    if k <= start[0][1]:
        print(depth.index(k) + 1)
    elif len(start) == 1:
        print(start[0][0])
    else:
        cnt = (k - start[0][1]) % (start[-1][1] - start[0][1] + 1)
        res = start[0][1] + cnt
        print(depth.index(res) + 1)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    tree = [[] for _ in range(n)]
    for idx, a in enumerate(A):
        tree[idx].append(a - 1)

    start = []
    depth = [0 for _ in range(n)]

    def dfs(v, p, d, cnt):
        depth[v] = d
        for u in tree[v]:
            if visited[u]:
                start.append([u + 1, depth[u], cnt + 1])
                return
            else:
                visited[u] = True
                dfs(u, v, d + 1, cnt + 1)
        return

    visited = [False for _ in range(n)]
    visited[0] = True
    dfs(0, -1, 0, 0)

    if k <= start[0][1]:
        print(depth.index(k) + 1)
    else:
        cnt = (k - start[0][1]) % (start[0][2] - start[0][1])
        res = start[0][1] + cnt
        print(depth.index(res) + 1)


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

import math
A, B, N = list(input().split())
A = float(A)
B = float(B)
N = int(N)

tmp_pre = 0
for i in range(1, N+1):
  tmp = math.floor(A*i/B) - A*math.floor(i/B)
  if tmp > tmp_pre:
    tmp_pre = tmp
print(int(tmp_pre))

### FIXED CODE ###

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

if B==1:
  print(0)
else:
  tb = B - 1
  tp_pre = 0
  while(True):
    tp = (A*tb)//B - A*(tb//B)
    if tp > tp_pre:
      tp_pre = tp
    tb += B
    if tb > N:
      break
  if (B > N):
    print((A*N)//B - A*(N//B))
  else:
    print(int(tp_pre))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))
            
            if x+dx*j==x2 and y+dy*j==y2:
                print(dp[x2][y2])
                exit()

        
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))
            elif dp[x+dx*j][y+dy*j]==dp[x][y]+1:continue###
            elif dp[x+dx*j][y+dy*j]<=dp[x][y]:break###
    
            
            if x+dx*j==x2 and y+dy*j==y2:
                print(dp[x2][y2])
                exit()

        
print(-1)
### BUGGY CODE ###

S = list(input())
N = len(S)
count = 0
for i in range(N - 3):
    for j in range(i + 3, N):
        if int("".join(S[i : j+1])) % 2019 == 0:
            count += 1
print(count)

### FIXED CODE ###

from collections import Counter
s = input()

n = len(s)
dp = [0] * (n + 1)

for i in range(n - 1, -1, -1):
    dp[i] = (dp[i + 1] + pow(10, (n - i - 1), 2019) * int(s[i])) % 2019

c = Counter(dp)

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

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

def gcd(a,b):
  if a%b==0:
    return b
  else:
    return gcd(b,a%b)

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
for x in a:
  if l%x!=0:
    g=gcd(l,x)
    l=l*x//g

for x in a:
  ans+=(l//x)%m

print(ans%m)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

'''def gcd(a,b):
  if a%b==0:
    return b
  else:
    return gcd(b,a%b)'''


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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
'''
for x in a:
  if l%x!=0:
    g=gcd(l,x)
    l=l*x//g
'''
l=lcm(*a)

for x in a:
  ans+=l//x

print(ans%m)