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

# -*- coding: utf-8 -*-

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
S = [input() for _ in range(H)]

A = [[-1 for _ in range(W)] for _ in range(H)]
A[Ch-1][Cw-1] = 0

def isValid(h,w):
  if h>=0 and h<H and w>=0 and w<W and S[h][w]=='.' and A[h][w]==-1:
    return True
  else:
    return False

warp = 0
BFS_now = [(Ch-1, Cw-1)]
BFS_search = [(Ch-1, Cw-1)]
ij = [(-1,0),(0,-1),(0,1),(1,0)]
while len(BFS_now)>0:
  while len(BFS_search)>0:
    BFS_search_tmp = []
    for h,w in BFS_search:
      for i,j in ij:
        if isValid(h+i,w+j):
          BFS_search_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp
    BFS_now += BFS_search_tmp
    BFS_search = BFS_search_tmp
  BFS_now_tmp = []
  for h,w in BFS_now:
    for i in range(-2,3):
      for j in range(-2,3):
        if isValid(h+i,w+j):
          BFS_now_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp + 1
  BFS_now = BFS_now_tmp
  BFS_search = BFS_now_tmp
  warp += 1

print(A[Dh-1][Dw-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
S = [input() for _ in range(H)]

A = [[-1 for _ in range(W)] for _ in range(H)]
A[Ch-1][Cw-1] = 0

def isValid(h,w):
  if h>=0 and h<H and w>=0 and w<W and S[h][w]=='.' and A[h][w]==-1:
    return True
  else:
    return False

warp = 0
BFS_now = [(Ch-1, Cw-1)]
BFS_search = [(Ch-1, Cw-1)]
ij = [(-1,0),(0,-1),(0,1),(1,0)]
while len(BFS_now)>0:
  while len(BFS_search)>0:
    BFS_search_tmp = []
    for h,w in BFS_search:
      for i,j in ij:
        if isValid(h+i,w+j):
          BFS_search_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp
    BFS_now += BFS_search_tmp
    BFS_search = BFS_search_tmp
  BFS_now_tmp = []
  for h,w in BFS_now:
    for i in range(-2,3):
      for j in range(-2,3):
        if isValid(h+i,w+j):
          BFS_now_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp + 1
  BFS_now = BFS_now_tmp
  BFS_search = BFS_now_tmp
  warp += 1

print(A[Dh-1][Dw-1])
### BUGGY CODE ###

#nCr % mod
def comb_mod(n, r, mod):
  x = 1
  y = 1
  for i in range(r):
    x = (x * (n - i)) % mod
    y = (y * (i + 1)) % mod
    
  ans = x * pow_k(y, mod-2, mod)
  
  return ans % mod
  
# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def main():
  MOD = 10 ** 9 + 7
  n,k = map(int,input().split())
  a = sorted(list(map(int,input().split())))
  
  ans = 0
  for i in range(n):
    if i-k+1 >= 0:
      ans += comb_mod(i,k-1,MOD) * a[i]
      
    if n-i-k >= 0:
      ans -= comb_mod(n-i-1,k-1,MOD) * a[i]
      
    ans %= MOD
      
  print(ans)

main()

### FIXED CODE ###

# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def main():
  MOD = 10 ** 9 + 7
  n,k = map(int,input().split())
  a = sorted(list(map(int,input().split())))
  
  g_k = 1
  for i in range(1,k):
    g_k *= i
    g_k %= MOD
    
  gyakugen = pow_k(g_k,MOD-2,MOD)
  array = [0] * (n+1)
  array[k-1] = g_k
  
  for i in range(k, n+1):
    array[i] = array[i-1] * i * pow_k(i-k+1,MOD-2,MOD)
    array[i] %= MOD
    
  ans = 0
  for i in range(n):
    if i-k+1 >= 0:        
      ans += array[i] * gyakugen * a[i]
      
    if n-i-k >= 0:
      ans -= array[n-i-1] * gyakugen * a[i]
      
    ans %= MOD
      
  print(ans)

main()
### BUGGY CODE ###

N, M, L = map(int, input().split())

INF = float('inf')
d1 = [[INF]*N for _ in range(N)]


for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d1[a][b] = c
    d1[b][a] = c
for i in range(N):
    d1[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            d1[i][j] = min(d1[i][k] + d1[k][j], d1[i][j])

d2 = [[INF]*N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            d2[i][j] = 0
        if d1[i][j] <= L and i != j:
            d2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if d2[s][t] == INF:
        print(-1)
    else:
        print(d2[s][t]-1)


### FIXED CODE ###

N, M, L = map(int, input().split())

INF = float('inf')
d1 = [[INF]*N for _ in range(N)]


for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d1[a][b] = c
    d1[b][a] = c
for i in range(N):
    d1[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            d1[i][j] = min(d1[i][k] + d1[k][j], d1[i][j])

d2 = [[INF]*N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            d2[i][j] = 0
        if d1[i][j] <= L and i != j:
            d2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if d2[s][t] == INF:
        print(-1)
    else:
        print(d2[s][t]-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
S = input()
h = [0]*N

for i, a in enumerate(S):
    if a=='R':
        h[i] = 0
    elif a=='G':
        h[i] = 1
    else:
        h[i] = 9

cnt = -1
ans = 0
for i in range(N):
    cnt = h[i]
    for j in range(i+1, N):
        num = cnt + h[j]
        if num == 1 or num == 9 or num==10:
            for k in range(j+1, N):
                if num + h[k] == 10 and k!=2*j-i:
                    ans += 1

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
S = input()
h = [0]*N
h = 'RGB'*1000

#h = h.replace('R', '1').replace('G', '2').replace('B', '7')
'''
cnt = -1
ans = 0
for i in range(N):
    cnt = int(h[i])
    for j in range(i+1, N):
        num = cnt + int(h[j])
        if num == 3 or num == 9 or num==8:
            for k in range(j+1, N):
                if num + int(h[k]) == 10 and k!=2*j-i:
                    ans += 1
'''

#h = h.replace('R', '1').replace('G', '2').replace('B', '7')

c_r = c_g = c_b = 0
h = ''
for i, a in enumerate(S):
    if a == 'R':
        c_r += 1
        h += '1'
    if a == 'G':
        c_g += 1
        h += '2'
    if a == 'B':
        c_b += 1
        h += '7'

ans = c_r * c_g * c_b

for i in range(N):
    for j in range(i+1, N):
        if 2*j-i<N and int(h[i]) + int(h[j]) + int(h[2*j-i]) == 10:
            ans -= 1
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
tmp = s
flag = 0
for _ in range(q):
    _s = input()
    t = 0
    f = 0
    c = ""
    if _s == "1":
        flag += 1
    else:
        t, f, c = _s.split(" ")
        r = flag % 2
        if f == "1" and r == 0:
            tmp = c + tmp
        elif f == "1" and r == 1:
            tmp = tmp + c
        elif f == "2" and r == 0:
            tmp = tmp + c
        elif f == "2" and r == 1:
            tmp = c + tmp
if flag % 2 == 0:
    print(tmp)
else:
    print(tmp[::-1])
        

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
tmp = deque()
for i in range(len(s)):
    tmp.append(s[i])
flag = 0
for _ in range(q):
    _s = input()
    if _s == "1":
        flag += 1
    else:
        t, f, c = _s.split(" ")
        r = flag % 2
        if f == "1" and r == 0:
            #tmp = c + tmp
            tmp.appendleft(c)
        elif f == "1" and r == 1:
            #tmp = tmp + c
            tmp.append(c)
        elif f == "2" and r == 0:
            #tmp = tmp + c
            tmp.append(c)
        elif f == "2" and r == 1:
            #tmp = c + tmp
            tmp.appendleft(c)
if flag % 2 == 0:
    for i in range(len(tmp)):
        print(tmp.popleft(), end="")
else:
    for i in range(len(tmp)):
        print(tmp.pop(), end="")
### BUGGY CODE ###

import heapq


class Prim():
    # 無向グラフであるという前提に注意
    def __init__(self, N):
        self.edge = [[] for i in range(N)]
        self.N = N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        0-indexedであることに注意、graph.add(u-1, v-1)とする必要がある
        """
        self.edge[u].append([d, v])  # コスト、e_toとなっていることに注意
        self.edge[v].append([d, u])

    def delete(self, u, v):
        self.edge[u] = [_ for _ in self.edge[u] if _[0] != v]
        self.edge[v] = [_ for _ in self.edge[v] if _[0] != u]

    def Prim(self):
        """
        return: 最小全域木のコストの和
        """
        used = [True] * self.N  # True:不使用
        edgelist = []
        for e in self.edge[0]:
            heapq.heappush(edgelist, e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            minedge = heapq.heappop(edgelist)
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            used[v] = False
            for e in self.edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, e)
            res += minedge[0]
        return res

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

G = Prim(N)

X = []
Y = []
for i in range(G.N):
    X.append((data[i][0],i))
    Y.append((data[i][1],i))

X = sorted(X)
Y = sorted(Y)

#辞書順で隣り合うものだけ考えれば良い

for i in range(G.N-1):
    G.add(X[i][1],X[i+1][1],X[i+1][0]-X[i][0])
    G.add(Y[i][1],Y[i+1][1],Y[i+1][0]-Y[i][0])

print(G.Prim())

### FIXED CODE ###

class Kruskal():
    def __init__(self,n):
        self.e = []
        self.par = [i for i in range(n+1)]  #親のノード番号
        self.rank = [0]*(n+1)
    def add(self,u,v,d):  #クラスカル法で考えるのは無向グラフ
        self.e.append([u,v,d])
    def find(self,x):  #xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  #x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def unite(self,x,y):  #x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1
    def Kruskal(self):
        edges = sorted(self.e,key=lambda x: x[2])  #距離でソート
        a = 0
        for e in edges:
            if not self.same_check(e[0],e[1]):
                self.unite(e[0],e[1])
                a += e[2]
        return a

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

G = Kruskal(N)

X = []
Y = []
for i in range(N):
    X.append((A[i][0], i))
    Y.append((A[i][1], i))

X = sorted(X)
Y = sorted(Y)

# 辞書順で隣り合うものだけ考えれば良い

for i in range(N - 1):
    G.add(X[i][1], X[i + 1][1], X[i + 1][0] - X[i][0])
    G.add(Y[i][1], Y[i + 1][1], Y[i + 1][0] - Y[i][0])

print(G.Kruskal())
### BUGGY CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    def depth(self):
    	ans = 0
    	for r in self.roots():
    		ans = max(ans, len(self.members(r)))
    	return ans

n,m = readInts()
ab = []
for i in range(m):
	ab.append(readInts())

uf = UnionFind(n+1)
for a,b in ab:
	uf.union(a,b)

print(uf.depth())

### FIXED CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def depth(self):
    	ans = 0
    	for r in self.roots():
    		ans = max(ans,self.size(r))
    	return ans

n,m = readInts()
ab = []
for i in range(m):
	ab.append(readInts())

uf = UnionFind(n+1)
for a,b in ab:
	uf.union(a,b)

print(uf.depth())
### BUGGY CODE ###

from math import factorial
n=int(input())
a=sorted(list(map(int,input().split())))
def f(n,r):
  return factorial(n) // factorial(r) // factorial(n - r)
ans=0
n=a[-1]
for j,i in enumerate(a):
  b=f(n,i)
  ans=max(ans,b)
  if b<ans:
    print(n,a[max(0,j-1)])
    exit()
print(n,a[-2]) 

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
l=a[-1]
b=[abs(i-l/2) for i in a]
c=float("inf")
for i in range(n-1):
  c=min(c,b[i])
print(l,a[b.index(c)])
### BUGGY CODE ###

import math

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

ab = abs(n - k)

while n > ab:
  n = ab
  ab = abs(n - k)

print(n)

### FIXED CODE ###

import math

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

amari = n % k
n = amari

ab = abs(n - k)

while n > ab:
  n = ab
  ab = abs(n - k)

print(n)
### BUGGY CODE ###

import itertools


X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [a + b for (a, b) in list(itertools.product(A, B))]
AB = sorted(AB)[::-1]
ans = [ab + c for (ab, c) in list(itertools.product(AB[:3000], C))]
ans = sorted(ans)[::-1]
for i in range(K):
    print(ans[i])


### FIXED CODE ###

import itertools


X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [a + b for (a, b) in list(itertools.product(A, B))]
AB.sort(reverse=True)
ans = [ab + c for (ab, c) in list(itertools.product(AB[:min(3000, X*Y*Z)], C))]
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

import sys
def input():
  return sys.stdin.readline().rstrip()
n, k = [int(i) for i in input().split()]
h = sorted(int(input()) for _ in range(n))
a = float("inf")
for i in range(n - k + 1):
  hik = h[i:i + k]
  a = min(a, max(hik) - min(hik))
print(a)

### FIXED CODE ###

import sys
def input():
  return sys.stdin.readline().rstrip()
n, k = [int(i) for i in input().split()]
h = sorted(int(input()) for _ in range(n))
print(min(h[i + k - 1] - h[i] for i in range(n - k + 1)))
### BUGGY CODE ###

K,S = map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        if x+y==S:
            count=count+1
        elif x+y<S:
            z=x+y
            for z in range(K+1):
                if x+y+z==S:
                    count=count+1
print(count)


### FIXED CODE ###

a,b=list(map(int,input().split()))
count=0
for x in range(a+1):
    for y in range(a+1):
        if b < x+y:
            break
        if b-x-y <= a:
            count+=1
print(count)
### BUGGY CODE ###

import numpy as np
n, W = map(int, input().split())
wv = []
for i in range(n):
    wv.append(list(map(int, input().split())))
dp = [0] * (W+1)

for w, v in wv:
    for j in range(W, w-1, -1):
        DP = dp[j-w] + v
        if dp[j] < DP:
            dp[j] = DP
print(dp[-1])

### FIXED CODE ###

def dp():
    n, W = map(int, input().split())
    wv = (map(int, input().split()) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in wv:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(dp())
### BUGGY CODE ###

n = int(input());
s = n - 1
for i in range(1,n):
    t = n / i
    if t.is_integer() == True and s > (t-1)+(i-1):
        s = (t-1)+(i-1)
print(int(s))

### FIXED CODE ###

import math
n = int(input());
s = n - 1
for i in range(1,int(math.sqrt(n))+1):
    t = n / i
    if t.is_integer() == True and s > (t-1)+(i-1):
        s = (t-1)+(i-1)
print(int(s))
### BUGGY CODE ###

#すべて1のところ
MOD = 10 ** 9 + 7
L = list(input())
N = len(L)


def calc(x): #1が続いている桁数
    if x == 0:
        return 1
    tmp_ans = 1
    tmp = 1
    for i in range(1, x):
        tmp = (tmp * (x + 1 - i))//i
        tmp_ans += pow(2, i, MOD) * tmp
        tmp_ans %= MOD

    tmp_ans += pow(2, x, MOD)
    tmp_ans %= MOD
    return tmp_ans

#ここまでで一番上の桁が0の場合を処理済み（N - 1桁で書ける場合）
ans = calc(N - 1) + 2
# print (ans)

# 1xxxxxxのxxxxxxの部分を足す必要がある

count = 1
for i in range(1, N):
    if L[i] == '1':
        ans += (2 ** count) * (calc(N - 1 - i) + 1)
        count += 1
        ans %= MOD
    
print (ans % MOD)

### FIXED CODE ###

# すべて1のところ
# 毎回calc(x)を計算しているから遅い
MOD = 10 ** 9 + 7
L = list(input())
N = len(L)

lst = [-1] * N
def calc(x): #1が続いている桁数
    if x == 0:
        return 1
    tmp_ans = 1
    tmp = 1
    for i in range(1, x):
        tmp = (tmp * (x + 1 - i))//i
        tmp_ans += pow(2, i, MOD) * tmp
        tmp_ans %= MOD

    tmp_ans += pow(2, x, MOD)
    tmp_ans %= MOD
    return tmp_ans

def calc1(x):
    return pow(3, x, MOD)

#ここまでで一番上の桁が0の場合を処理済み（N - 1桁で書ける場合）
ans = calc1(N - 1) + 2
# print (ans)

# 1xxxxxxのxxxxxxの部分を足す必要がある

count = 1
for i in range(1, N):
    if L[i] == '1':
        ans += pow(2, count, MOD) * (calc1(N - 1 - i) + 1)
        count += 1
        ans %= MOD
    
print (ans % MOD)
### BUGGY CODE ###

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

mod = 10 ** 9 + 7
k = k % mod
mod2 = 2 ** (mod-2) % mod
# 配列内で自身より小さい数の個数　前後別に求める
b = [[0, 0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i > j:
                b[i][0] += 1
            elif i < j:
                b[i][1] += 1
    b[i][0] = b[i][0] % mod
    b[i][1] = b[i][1] % mod
ans = 0
# kまでの和　後ろの数用
sigmakp = (((k * (k+1)) % mod) * mod2) % mod
#sigmakp = int(sigmakp)
# k-1までの和　前の数用
sigmakn = (((k * (k-1)) % mod) * mod2) % mod
#sigmakn = int(sigmakn)

for i in range(n):
    mae = (sigmakp * b[i][1]) % mod
    ushiro = (sigmakn * b[i][0]) % mod
    ans = ((mae + ushiro) % mod + ans) % mod 
print(ans)

### FIXED CODE ###

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

mod = 10 ** 9 + 7
k = k % mod
# 配列内で自身より小さい数の個数　前後別に求める
b = [[0, 0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i > j:
                b[i][0] += 1
            elif i < j:
                b[i][1] += 1
    b[i][0] = b[i][0] % mod
    b[i][1] = b[i][1] % mod
ans = 0

if k%2 == 0:
    sigmakp = (int(k/2) * (k+1)) % mod
    sigmakn = (int(k/2) * (k-1)) % mod
else:
    sigmakp = (int((k+1)/2) * k) % mod
    sigmakn = (int((k-1)/2) * k) % mod

for i in range(n):
    mae = (sigmakp * b[i][1]) % mod
    ushiro = (sigmakn * b[i][0]) % mod
    ans = ((mae + ushiro) % mod + ans) % mod 
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
c1 = s
for i in range(k+1):
    if 0 <= s-i <= 2*k:
        for j in range(0, k+1):
            if 0<= s-i-j <= k:
                for l in range(0,k+1):
                    if i + j + l == s:
                        count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0
for i in range(k+1):
    for j in range(k+1):
        if 0<= s-i-j <= k:
            cnt += 1
print(cnt)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def sizes(self):
        return [self.size(i) for i in self.roots() if self.size(i) != 1]

N, M = map(int,input().split())
UFT = UnionFind(N)
bridges = []
for _ in range(M):
    bridges.append(list(map(int,input().split())))
bridges.reverse()

ans = []
for A, B in bridges:
    UFT.union(A-1, B-1)
    cnt = 0
    for i in UFT.sizes():
        cnt += (i*(i-1)) // 2
    ans.append(cnt)

ALL = N*(N-1)//2
ans = list(map(lambda x: ALL - x, ans))
ans.reverse()
ans.append(ALL)
for i in range(1,M+1):
    print(ans[i])

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
UFT = UnionFind(N)
bridges = []
for _ in range(M):
    A, B = map(int,input().split())
    bridges.append((A-1, B-1))
bridges.reverse()

ans = [N * (N-1) // 2]
for i in range(M-1):
    temp = ans[-1]
    A, B = bridges[i]
    if not UFT.same(A, B):
        temp -= UFT.size(A) * UFT.size(B)
        UFT.union(A, B)
    ans.append(temp)

ans.reverse()
for a in ans:
    print(a)