Harryxun/stf_run huggingface dataset:
h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][1] = 0
    dist[i][-1] = 0
    dist[i][-2] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[1][j] = 0
    dist[-1][j] = 0
    dist[-2][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+2][j+2] = 0

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        di, dj = d_b[v][0]+i, d_b[v][1]+j
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][-1] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[-1][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)
a = input()
b= input()
print(a*b)

### FIXED CODE ###

A,B =map(int,input().split())
print(A*B)
[a,b,k]=[int(i) for i in input().split()]
s=list(range(a,b+1))
#print(s)
if (2*k)<=(b-a+1):
    for i in range(k):
        print(int(s[i]))
    for i in range(k):
        print(int(s[b-a-(k-i-1)]))
else:
    for i in range(b-a+1):
        print(s[i])


### FIXED CODE ###

[a,b,k] = [int(i) for i in input().split()]

if k > (b-a+1):
    for i in range(a,b+1):
        print(i)
else:
    for i in range(a,a+k):
        print(i)
    for i in range(max(a+k,b-k+1),b+1):
        print(i)
n=int(input())
a+=list(map(int,input().split()))
c=0
for i in range(n-1):
  if a[i]!=i+1:
    c+=1
print("YES" if c<3 else "NO")
  


### FIXED CODE ###

a,b=map(int, input().split())
print("IMPOSSIBLE" if (a+b)%2 else int((a+b)/2))
n = int(input())
a_str = input().split()
a_num = [int(a) for a in a_str]
a_array = np.array(a_num)

rate_list = [1,400,800,1200,1600,2000,2400,2800,3200]

count = 0

for i in range(8):
    if len(a_array[np.where((a_array>=rate_list[i])&(a_array<rate_list[i+1]))]):
        count += 1

min_count = count

count += len(a_array[a_array>=rate_list[8]])
max_count = min(count,8)

print(str(min_count)+" "+str(max_count))

### FIXED CODE ###

import numpy as np

n = int(input())
a_str = input().split()
a_num = [int(a) for a in a_str]
a_array = np.array(a_num)

rate_list = [1,400,800,1200,1600,2000,2400,2800,3200]

count = 0

for i in range(8):
    if len(a_array[np.where((a_array>=rate_list[i])&(a_array<rate_list[i+1]))]):
        count += 1

if count == 0:
    min_count = 1
else:
    min_count = count

count += len(a_array[a_array>=rate_list[8]])
max_count = count

print(str(min_count)+" "+str(max_count))
# 帰宅経路数と時間を取得
N, T = map(int, input().split())
# 時間制限
ans = 1001
# N個の帰宅経路と時間を取得し、比較する
for i in range(N):
    cost, time = map(int, input().split())
    if time <＝ T:
        ans = min(ans, cost)
# 出力する
if ans == 1001:
    print("TLE")
else:
    print(ans)

### FIXED CODE ###

n, l = map(int, input().split())
ans = 1001
for i in range(n):
    c, t = map(int, input().split())
    if t <= l:
        ans = min(ans, c)
if ans == 1001:
    ans = "TLE"
print(ans)
import math

N = int(input())
if N % 2 == 1:
  print(0)
else:
  zero_count = 0
  for i in range(1,1+int(math.log(N/2,5)//1)):
    zero_count += (N/2)//5**i
  print(int(zero_count))

### FIXED CODE ###

import math

N = int(input())
if N % 2 == 1:
  print(0)
else:
  zero_count = 0
  if N == 0:
    print(0)
  else:  
    for i in range(1,1+int(math.log(N//2,5)//1)):#ここのN//2がN/2にしてただけで計算が狂った。floatの扱いの問題か
      zero_count += (N//2)//(5**i)
    print(int(zero_count))
N = int(input())
R = int(input())
if N < 10:
    print(1000-100*N)
else:
    print(R)

### FIXED CODE ###

N,R= map(int,input().split())
if N < 10:
    print(R+100*(10-N))
else:
    print(R)
s = input()
if len(s)>=4 and s[:4] = "YAKI":
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s = input()
if len(s)>=4 and s[:4] == "YAKI":
  print("Yes")
else:
  print("No")
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dict[tmp[d]] = str(i)+' '+str(d)
result ={}
cost ={}
dict[0] = 0
def calcost(L,R,D):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        posi1 = dict[R].split()
        posi2 = dict[str(int(R)-D)].split()
        costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        if str(int(R)-D) in cost:
            cost[R] = costs + cost[str(int(R)-D)]
            return cost[R]
        else:
            cost[R] = costs + calcost(L,str(int(R)-D),D)
            return cost[R]

for n in range(D+1,H*W+1):
    calcost(str(1),str(n),D)

Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = cost[tmp[1]]-cost[tmp[0]]
        print(result[tmpx])

### FIXED CODE ###

tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dictx ={}
dicty ={}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dictx[tmp[d]] = i
        dicty[tmp[d]] = d
cost ={}
def calcost(R):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        costs = abs(dictx[R]-dictx[str(int(R)-D)]) + abs(dicty[R]-dicty[str(int(R)-D)])
        cost[R] = costs + cost[str(int(R)-D)]
        return cost[R]

for n in range(1,H*W+1):
    calcost(str(n))
Q = int(input())
for j in range(Q):
    tmp = input().split()
    print(str(cost[tmp[1]]-cost[tmp[0]]))
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
Cm = []
Cp = []
for i in range(N):
	if(A[i]-B[i]<0):
		Cm.append(A[i]-B[i])
	elif(A[i]-B[i]>0):
		Cp.append(A[i]-B[i])
Cm.sort()
Cp.sort()


if(len(Cm) == 0):
	print(0)
	exit(1)
if(sum(Cp)<abs(sum(Cm))):
	print(-1)
	exit(1)

j=0
i = 0
nowCp = int(Cp[len(Cp)-i-1])


while(j<len(Cm)):
	if(nowCp>=abs(Cm[j])):
		nowCp -= abs(Cm[j])
		j += 1
	elif(nowCp<abs(Cm[j]) and i<len(Cp)):
		i += 1
		nowCp += int(Cp[len(Cp)-i-1])

	else:
		break
	

if(j == len(Cm)):
	print(j+i+1)
else:
	print(-1)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
Cm = []
Cp = []
for i in range(N):
	if(A[i]-B[i]<0):
		Cm.append(A[i]-B[i])
	elif(A[i]-B[i]>0):
		Cp.append(A[i]-B[i])
Cm.sort()
Cp.sort()


if(len(Cm) == 0):
	print(0)
	exit(0)
if(sum(Cp)<abs(sum(Cm))):
	print(-1)
	exit(0)

j=0
i = 0
nowCp = int(Cp[len(Cp)-i-1])


while(j<len(Cm)):
	if(nowCp>=abs(Cm[j])):
		nowCp -= abs(Cm[j])
		j += 1
	elif(nowCp<abs(Cm[j]) and i<len(Cp)):
		i += 1
		nowCp += int(Cp[len(Cp)-i-1])

	else:
		break
	

if(j == len(Cm)):
	print(j+i+1)
else:
	print(-1)
n = int(input())
a = list(map(int,input().split()))
q = int(input())
u = []
for i in range(q):
    u.append(tuple(map(int,input().split())))

from collections import Counter
z = Counter(a)

sum = sum(a)
for i in range(q):
    try:
        rev = z.pop(u[i][0])
        sum+=(u[i][1]-u[i][0])*rev
        print(sum)
    except KeyError:
        print(sum)
    if u[i][1] in z.keys():
        z[u[i][1]]+=rev
    else:
        z[u[i][1]]=rev

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
u = []
for i in range(q):
    u.append(tuple(map(int,input().split())))

from collections import Counter
z = Counter(a)

sum = sum(a)
for i in range(q):
    try:
        rev = z.pop(u[i][0])
        sum+=(u[i][1]-u[i][0])*rev
        print(sum)
        if u[i][1] in z:
            z[u[i][1]]+=rev
        else:
            z[u[i][1]]=rev
    except KeyError:
        print(sum)
from import math
r = raw_input()
area = r * r * math.pi
cir = 2 * r * math.pi
print '%f %f' % (area, cir)

### FIXED CODE ###

import math
r = input()
area = r * r * math.pi * 1.0
cir = 2 * r * math.pi * 1.0
print '%f %f' % (area, cir)
S = input()
stack = []

for s in S:
  if s == 'B':
    stack.pop()
  else:
    stack.append(s)
    
    
print(*stack, sep = '')

### FIXED CODE ###

s = input()
ans = ''

for str_i in s:
  if str_i == '0':
    ans += '0'
  elif str_i == '1':
    ans += '1'
  elif str_i == 'B':
    ans = ans[:len(ans)-1]
    
print(ans)
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP
from sys import setrecursionlimit(1000000)


CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 1 or n == 2:
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = 0
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0])
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 1)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1])
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    for i in holes:
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    unable = check_hole(M, broken_stairs)
    if not unable:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(ans % 1000000007)

### FIXED CODE ###

import sys

n, m = list(map(int, input().split()))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7

for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])
while 1:
  H, W = map(int, raw_input().stlip())
  for i in range(H):
    print "#" * W 

### FIXED CODE ###

while 1:
  h, w = map(int, raw_input().split())
  if h == 0 and w == 0:
    break
  for i in range(h):
    print "#" * w
  print""
MAX = 600000
MOD = 10 ** 9 + 7
fac = [0] * MAX
ifac = [0] * MAX
fac[0] = 1
for i in range(1,MAX):
    fac[i] = (fac[i-1] * i) % MOD
ifac[MAX-1] = pow(fac[MAX-1],MOD-2,MOD)
for i in reversed(range(1,MAX)):
    ifac[i-1] = (ifac[i] * i) % MOD

def combinations(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return (fac[n] * ifac[k] * ifac[n-k]) % MOD

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

def f(A):
    ans = 0
    for i in range(K-1,N):
        ans += A[i]*combinations(i-1,K-1)
        ans %= MOD
    return ans

print((f(A) - f(reversed(A))) % MOD )



### FIXED CODE ###

MAX = 600000
MOD = 10 ** 9 + 7
fac = [0] * MAX
ifac = [0] * MAX
fac[0] = 1
for i in range(1,MAX):
    fac[i] = (fac[i-1] * i) % MOD
ifac[MAX-1] = pow(fac[MAX-1],MOD-2,MOD)
for i in reversed(range(1,MAX)):
    ifac[i-1] = (ifac[i] * i) % MOD

def combinations(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return (fac[n] * ifac[k] * ifac[n-k]) % MOD


N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
com = [0]
for i in range(N):
    com.append(A[i] + com[-1])
#print(com)
ans = 0
for i in range(K-2,N-1):
    ans += combinations(i,K-2) * (-(com[N-i-1]) + (com[N]-com[i+1]))
    #print(N-i-1,N,i+1)
    ans %= MOD
    #print(combinations(i,K-2) * (-(com[N-i-1]) + (com[N]-com[i+1])))
print(ans)
# from math import gcd
from fraction import gcd

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in a:
    ans = ans * i // gcd(ans, i)
mod = 10**9+7
print(sum(map(lambda x: ans // x, a)) % mod)

### FIXED CODE ###

# from math import gcd
from fractions import gcd

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in a:
    ans = ans * i // gcd(ans, i)
mod = 10**9+7
print(sum(map(lambda x: ans // x, a)) % mod)
import math
A,B,C,D = [int(i) for i in input().split()]

l= (C * D) // math.gcd(C, D)

s=B - A + 1 - (((B//C - (A-1)//C))+(B//D - (A-1)//D)-(B//l)-((A-1)//l))
print(s)


### FIXED CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
abcd = input().split(" ")
a = int(abcd[0])
b = int(abcd[1])
c = int(abcd[2])
d = int(abcd[3])
cd = lcm(c, d)
print(b-a-(b//c-((a-1)//c + 1))-(b//d - ((a-1)//d + 1))+(b//cd-((a-1)//cd + 1)))
n = int(input())
power = 1

for i in range(1,n+1):
  power = power * i
  
print(powe r% (pow(10,9) + 7))

### FIXED CODE ###

INF = 1000000007
n = int(input())

ans = 1


for i in range(1,n+1):
  ans = ans * i % INF
  
print(ans)
o, e = [input().rstrip() for i in range(2)]
lst = []
for i in len(o):
    print(o[i], end='')

    if i + 1 > len(e):
        print()
        break
    else:
        print(e[i], end='')

### FIXED CODE ###

o, e = [input().rstrip() for i in range(2)]
lst = []
for i in range(len(o)):
    print(o[i], end='')

    if i + 1 > len(e):
        print()
        break
    else:
        print(e[i], end='')
a = int(input())

c = a*a * 3.14
r = (a+a) * 3.14

print (c,r)

### FIXED CODE ###

import math

a = float(input())

c = a*a * math.pi
r = (a+a) * math.pi

print (float(c),float(r))
r, g, b, n = map(int, input().split())
count = 0

for a in range(n+1):
  for c in range(n+1):
    Bb = N - r*a - g*c
    if Bb > N:
      if Bb % 2 == 0:
        count += 1
    else:
      break

print(count)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
count = 0

for a in range(n+1):
  for c in range(n+1):
    Bb = n - r*a - g*c
    if Bb >= 0:
      if Bb % b == 0:
        count += 1
    else:
      break

print(count)
def main15():
    strbuf1 = input('');
    strbuf2 = input('');
    strbufs1 = strbuf1.split();
    strbufs2 = strbuf2.split();
    buf1 = [];
    buf2 = [];
    ba = 0;
    for i in range(2):
        buf1.append(int(strbufs1[i]));
    for i in range(buf1[0]):
        buf2.append(int(strbufs2[i]));
        if(buf2[i] == 1):
            ba = i;
            break;
    are = buf1[1] - 1;
    kai1 = math.ceil(ba/are);
    kk = ba - are * kai1;
    kai2 = math.ceil((buf1[0] -(ba+1+kk))/are)
    print(int(kai1+kai2));

def main16():
    strbuf = input('');
    num = int(strbuf);
    kazu = 0;
    number = 1;
    while(kazu<num):


        kazu = kazu + 1;

        number = number + 1;


if __name__ == '__main__':
    main15()

### FIXED CODE ###

import math
def main15():
    strbuf1 = input('');
    strbuf2 = input('');
    strbufs1 = strbuf1.split();
    strbufs2 = strbuf2.split();
    buf1 = [];
    buf2 = [];
    ba = 0;
    for i in range(2):
        buf1.append(int(strbufs1[i]));
    for i in range(buf1[0]):
        buf2.append(int(strbufs2[i]));
        if(buf2[i] == 1):
            ba = i;
            break;
    are = buf1[1] - 1;
    kai1 = math.ceil(ba/are);
    kk = are * kai1 - ba;
    kai2 = math.ceil((buf1[0] -(ba+1+kk))/are)
    print(int(kai1+kai2));

def main16():
    strbuf = input('');
    num = int(strbuf);
    kazu = 0;
    number = 1;
    while(kazu<num):


        kazu = kazu + 1;

        number = number + 1;


if __name__ == '__main__':
    main15()
a,b=(int(x) for x in input().split())
num_list = list(map(int, input().split())).sort
ans = 0

for i in range(b):
  ans += num_list[i]

print(ans)


### FIXED CODE ###

a,b=(int(x) for x in input().split())
num_list = list(map(int, input().split()))
num_list.sort()
ans = 0
 
for i in range(b):
  ans += num_list[i]
 
print(ans)
S=str(input())
Q=int(input())
which=0
front=""
back=""
for i in range(Q):
    a=list(map(str,input().split()))
    if a==["1"]:
        which+=1
        which%=2
        continue
    else:
        if which==0:
            if a[1]=="1":
                front=a[2]+front
            if a[1]=="2":
                back+=a[2]
        if which==1:
            if a[1]=="1":
                back+=a[2]
            if a[1]=="2":
                front=a[2]+front
S=front+S+back
if which==1:
    print(S[::-1])
if which==0:
    print(S)

### FIXED CODE ###

check=str(input())
if check=="AAA" or check=="BBB":
    print("No")
else:
    print("Yes")
NNN = input()

S = str(input())
T = str(input())

S_list =list(S)
T_list =list(T)

N = len(S_list)
outstr = []

for n in range(N*2):
    if n%2 == 0:
        outstr.append(S_list[int(n / 2)])
    else:
        outstr.append(T_list[int(n / 2)])

STR = ','.join(outstr)
STR2 = STR.replace(",", "")
print(STR2)


### FIXED CODE ###


NNN = input()

S,T = map(str, input().split())

S_list =list(S)
T_list =list(T)

N = len(S_list)
outstr = []

for n in range(N*2):
    if n%2 == 0:
        outstr.append(S_list[int(n / 2)])
    else:
        outstr.append(T_list[int(n / 2)])

STR = ','.join(outstr)
STR2 = STR.replace(",", "")
print(STR2)
MOD = 10 ** 9 + 7
import numpy as np
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

# 前計算
for i in range(n - 1):
    x[i] = x[i + 1] - x[i]

for i in range(m - 1):
    y[i] = y[i + 1] - y[i]

N = [n - 1]
for i in range((n)//2 - 1):
    N.append((N[i] + (n - 1 - 2 * (i + 1))) % MOD)

M = [m - 1]
for i in range((m)//2 - 1):
    M.append((M[i] + (m - 1- 2 * (i + 1))) % MOD)

if N[0] % 2 == 0:
    N += N[::-1]
else:
    N += N[1::-1]
if M[0] % 2 == 0:
    M += M[::-1]
else:
    M += M[1::-1]

# print (N)
# print (M)

N = np.array(N, dtype = 'int64')
M = np.array(M, dtype = 'int64')

X = np.array(x[:-1], dtype = 'int64')
Y = np.array(y[:-1], dtype = 'int64')

# print (N)
# print (M)
# print (X)
# print (Y)

X *= N
Y *= M

X %= MOD
Y %= MOD

# print (X)
# print (Y)
# print ((np.sum(X) * np.sum(Y)) % MOD)

X_sum = np.sum(X) % MOD
Y_sum = np.sum(Y) % MOD

print ((X_sum * Y_sum) % MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

# 前計算
for i in range(n - 1):
    x[i] = x[i + 1] - x[i]

for i in range(m - 1):
    y[i] = y[i + 1] - y[i]

N = [n - 1]
for i in range(n - 3, 0, -2):
    N.append(N[-1] + i)
    # N.append((N[i] + (n - 1 - 2 * (i + 1))) % MOD)

M = [m - 1]
for i in range(m - 3, 0, -2):
    M.append(M[-1] + i)
    # M.append((M[i] + (m - 1- 2 * (i + 1))) % MOD)

if N[0] % 2 == 0:
    N += N[::-1]
elif N[0] != 1:
    N += N[-2::-1]

if M[0] % 2 == 0:
    M += M[::-1]
elif M[0] != 1:
    M += M[-2::-1]

# print (x)
# print (y)
# print (N)
# print (M)

if len(x) - 1 > len(N):
    while True:
        pass

if len(y) - 1 > len(M):
    while True:
        pass


X_sum = 0
for i in range(n - 1):
    X_sum += x[i] * N[i]
    X_sum %= MOD

Y_sum = 0
for i in range(m - 1):
    Y_sum += y[i] * M[i]
    Y_sum %= MOD

print ((X_sum * Y_sum) % MOD)
import math

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

A,B,C,D = map(int,input().split())
E = lcm(C, D)
sample = B-A
ans = sample - ((B//C-A//C) + (B//D-A//D)-(B//E-A//E))
print(ans)

### FIXED CODE ###

S = input()
if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    print("Bad")
else:
    print("Good")
import sys
input = sys.stdin.readline

from itertools import accumulate

fact = [1]

for i in range(1, 2 * 10 ** 3 + 1):
    fact.append(fact[-1] * i)


def comb(n, r):
    return int(fact[n] / fact[r] / fact[n-r])


def main():
    n = int(input())
    l = list(map(int, input().split()))

    nums = [0] * 1001

    for e in l:
        nums[e] += 1

    acm = list(accumulate(nums))

    l.sort()
    ans = 0
    tmp = [0] * 1001
    tmp2 = [[0] * 1001 for _ in range(1001)]
    for i in range(n-2):
        for j in range(i+1, n-1):
            a = l[i]
            b = l[j]
            k = min(1000, a+b-1)

            # b < c のときの数
            cnt = acm[k] - acm[b]

            # b == c のときの補正
            if nums[b] >= 3 and a == b and tmp[b] == 0:
                cnt += comb(nums[b], 3)
                tmp[b] = 1

            if nums[b] >= 2 and a != b and tmp2[a][b] == 0:
                cnt += comb(nums[b], 2) * nums[a]
                tmp2[a][b] = 1

            ans += cnt

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

from bisect import bisect_left


def main():
    n = int(input())
    l = list(map(int, input().split()))

    l.sort()

    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            a = l[i]
            b = l[j]
            mx = bisect_left(l, a + b)
            ans += mx - j - 1

    print(ans)


if __name__ == "__main__":
    main()
n=input()
a=[int(i) for i in raw_input().split()]
s=0
a.sort()
for i in range(1,n):
  s+=a[i]
 print s

### FIXED CODE ###

n=input()
a=[int(i) for i in raw_input().split()]
a.sort()
s=a[n-1]
for i in range(n/2,n-1):
  s+=a[i]*2
if(n%2==1):
  s-=a[n/2]
print s
print('A' + input()[8] + 'C')


### FIXED CODE ###

a, b, x = map(int, input().split())
print(b // x - (a - 1) // x)
h,n = map(int,input().split())
li2=[input() for i in range(n)]
ab = []
for i in range(n):
    ab.append( [int(x.strip()) for x in li2[i].split()])
w = (int(h/ab[0][0])+1) * ab[0][1]
dp = [[0] * (w+1) for i in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j < ab[i][1]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i+1][j-ab[i][1]]+ab[i][0])

ans = 0
for i in range(w+1):
    if dp[n][i] >= h:
        print(i)
        exit()

### FIXED CODE ###

a = list(map(int, input().split()))
HP = a[0]

x = []
for i in range(a[1]):
    x1, y1 = [int(i) for i in input().split()]
    x.append((x1, y1))

max_tup = max(x, key=lambda x: x[0])
max_a = max_tup[0]
dp = [0] * (HP + max_a)

for i in range(1, len(dp)):
    dp[i] = min(dp[i - a] + b for a, b in x)

print(dp[HP])