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

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

r_idx = []
g_idx = []
b_idx = []

for i, s in enumerate(S):
  if s == "R":
    r_idx.append(i)
  elif s == "G":
    g_idx.append(i)
  elif s == "B":
    b_idx.append(i)
    
count = 0
for r in r_idx:
  for g in g_idx:
    for b in b_idx:
      if b==2*g-r or g==2*r-b or r==2*b-g:
        continue
      else:
        count += 1
        
print(count)

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            continue
        k = 2*j - i
        if j < k < n and s[i] != s[k] and s[j] != s[k]:
            cnt += 1
print(s.count('R') * s.count('G') * s.count('B') - cnt)
### BUGGY CODE ###

k=int(input())
import math
def ggcd(a,b,c):
    return math.gcd(math.gcd(a,b),math.gcd(a,c))
a=0
for i in range(1,1+k):
    for j in range(1,1+k):
        for l in range(1,1+k):
            a+=ggcd(i,j,l)
print(a)

### FIXED CODE ###

k=int(input())
import math
def ggcd(a,b,c):
    return math.gcd(math.gcd(a,b),math.gcd(a,c))
a=0
for i in range(1,1+k):
    for j in range(1,1+k):
        for l in range(1,1+k):
            a+=ggcd(i,j,l)
print(a)
### BUGGY CODE ###

import sys
import math
from fractions import gcd
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

# input = sys.stdin.readline


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def check(n, ans):
    for v in n:
        if v in ans and v != 1:
            return False

    return True


def main():
    a, b = map(int, input().split())

    ans = []

    nums = make_divisors(gcd(a, b))
    nums.sort()

    for n in nums:
        if check(make_divisors(n), ans):
            ans.append(n)

    print(len(ans))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
from fractions import gcd
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

# input = sys.stdin.readline


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def check(n, ans):
    for v in n:
        if v in ans and v != 1:
            return False

    return True


def main():
    a, b = map(int, input().split())

    ans = []

    nums = make_divisors(gcd(a, b))
    nums.sort()

    for n in nums:
        if check(make_divisors(n), ans):
            ans.append(n)

    print(len(ans))


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

def permutation_modp(n,k):
    ans=1
    for i in range(k):
        ans*=(n-i)
    return ans%1000000007
num_vertax,num_coler=map(int,input().split())
ver_array=[0]*num_vertax
for i in range(num_vertax-1):
    a,b=map(int,input().split())
    ver_array[a-1]+=1
    ver_array[b-1]+=1
ans=num_coler
ans*=permutation_modp(num_coler-1,ver_array.pop(0))
for ver in ver_array:
    ans*=permutation_modp(num_coler-2,ver-1)
print(ans%1000000007)

### FIXED CODE ###

N,K=map(int,input().split())
mod=1000000007
path=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  path[a].append(b)
  path[b].append(a)
#print(path)
  
abc=[False for i in range(N)] #0ならまだ塗ってない
 
abc[0]=True
cnt=0
ans=K%mod
nx=[]
for i in range(len(path[0])):
  child=path[0][i]
  if abc[child]:
    continue
  ans=ans*(K-1-cnt)
  ans=ans%mod
  cnt=cnt+1
  abc[child]=True
  nx.append(child)
while len(nx)>0:
  a=nx.pop()
  cnt=0
  for i in range(len(path[a])):
    child=path[a][i]
    if abc[child]:
      continue
    ans=ans*(K-2-cnt)
    ans=ans%mod
    cnt=cnt+1
    abc[child]=True
    nx.append(child)
      
print(ans%mod)
### BUGGY CODE ###

H,W,D = map(int,input().split())
A = {}
for i in range(H):
    l = list(map(int,input().split()))
    for j in range(W):
        A[l[j]-1] = [i+1,j+1]

Q = int(input())
LR = []
for i in range(Q):
    LR.append(list(map(int,input().split())))


for i in range(Q):
    ans = 0
    now = A[LR[i][0]-1]
    for j in range(D,LR[i][1] - LR[i][0]+D,D):
        will = A[LR[i][0]-1+j]
        ans += (abs(will[0] - now[0]) + abs(will[1] - now[1]))
        now = will

    print(ans)


### FIXED CODE ###

H,W,D = map(int,input().split())
A = {}
for i in range(H):
    l = list(map(int,input().split()))
    for j in range(W):
        A[l[j]] = [i+1,j+1]

Q = int(input())
LR = []
for i in range(Q):
    LR.append(list(map(int,input().split())))


ru = {}
for i in range(1,D+1):
    ru[i] = [0]

for i in range(1,D+1):
    c = 1
    while i + D*c <= H*W:
        now = A[i+D*(c-1)]
        will = A[i+D*c]
        mp = abs(will[0] - now[0]) + abs(will[1] - now[1])
        ru[i].append(mp + ru[i][c-1])
        c += 1

for i in range(Q):
    t = LR[i][0] % D
    if t == 0:
        t = D
        print(ru[t][LR[i][1]//D-1] - ru[t][LR[i][0]//D-1])
    else:
        print(ru[t][LR[i][1]//D] - ru[t][LR[i][0]//D])
### BUGGY CODE ###

# coding: utf-8
# Your code here!

counter = 0

string = input()

while (string.find("01") != -1 ) :
    string = (string.replace("01", "", 1))
    counter += 2

while (string.find("10") != -1 ) :
    string = (string.replace("10", "", 1))
    counter += 2
    
print(counter)

### FIXED CODE ###

# coding: utf-8
# Your code here!

counter = 0

string = input()

num_0 = string.count("0")
num_1 = string.count("1")

print(min(num_0, num_1)*2)
### BUGGY CODE ###

n = int(input())
lst = list(map(int, input().split()))
zero = False
fl = False
x = 1
for i in lst:
    if(i==0):
        zero = True
        break
    x*=i
    if(x>1e18):
        fl = True
if zero:
    print(0)
elif fl:
    print(-1)
else:
    print(x)

### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
zero = False
fl = False
x = 1
for i in lst:
    if(i==0):
        zero = True
        break
    if not fl:
        x*=i
    if(x>1e18):
        fl = True
if zero:
    print(0)
elif fl:
    print(-1)
else:
    print(x)
### BUGGY CODE ###

def main():
    n, *a, = map(int, open(0).read().split())
    m = max(a)

    def minimum_prime(x):
        if x == 1:
            return 1
        for i in range(3, x + 1, 2):
            if x % i == 0:
                return i

    d = [minimum_prime(i) if i % 2 == 1 else 2 for i in range(m + 1)]

    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    c = primes(a[0])
    f = 0
    for i in a:
        primes = set()
        while i != 1:
            p = d[i]
            primes.add(p)
            i = i // d[i]
        if b & primes:
            f = 1
        b |= primes
        c &= primes

    if f == 0:
        ans = "pairwise coprime"
    elif len(c) == 0:
        ans = "setwise coprime"
    else:
        ans = "not coprime"

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, *a, = map(int, open(0).read().split())
    m = max(a)

    d = [0] * (m+1)
    d[1] = 1
    for i in range(2, m+1):
        for j in range(i, m+1, i):
            if d[j] == 0:
                d[j] = i

    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    c = primes(a[0])
    f = 1
    for i in a:
        ps = set()
        while i != 1:
            p = d[i]
            ps.add(p)
            i = i // d[i]
        if f:
            if b & ps:
                f = 0
            b |= ps
        c &= ps

    if f:
        ans = "pairwise coprime"
    elif len(c) == 0:
        ans = "setwise coprime"
    else:
        ans = "not coprime"

    print(ans)


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

import sys
input = sys.stdin.readline

S = input().rstrip()
Q = int(input())

ans = S
for _ in range(Q):
    query = list(input().split())
    if query[0] == '1':
        ans = ans[::-1]
        continue
    elif query[0] == '2':
        f = query[1]
        c = query[2].rstrip()
        if f == '1':
            ans = c + ans
        else:
            ans = ans + c
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

S = input().rstrip()
Q = int(input())
head = ''
tail = ''
rev = False

for _ in range(Q):
    query = list(input().split())
    if query[0] == '1':
        if rev:
            rev = False
        else:
            rev = True
    elif query[0] == '2':
        f = query[1]
        c = query[2].rstrip()
        if f == '1':
            if rev:
                tail = tail + c
            else:
                head = c + head
        else:
            if rev:
                head = c + head
            else:
                tail = tail + c
if rev:
    tmp = head + S + tail
    print(tmp[::-1])
else:
    print(head + S + tail)
### BUGGY CODE ###

S = str(input())
Q = int(input())
Qer = [list(map(str,input().split())) for i in range(Q)]
flag = 0
for i in range(Q):
    if Qer[i][0] == "1":
        flag+=1
    else:
        if flag%2 ==0:
            if Qer[i][1] =="1":
                S = Qer[i][2] + S
            else:
                S = S+Qer[i][2]
        else:
            if Qer[i][1] =="2":
                S = Qer[i][2] + S
            else:
                S = S+Qer[i][2]

print(S if flag%2==0 else S[::-1])

### FIXED CODE ###

from collections import deque
S = str(input())
Q = int(input())
Qer = [list(map(str,input().split())) for i in range(Q)]
flag = True
anss = deque(S)
for i in range(Q):
    if Qer[i][0] == "1":
        flag = not flag
    else:
        if flag ==True:
            if Qer[i][1] =="1":
                anss.appendleft(Qer[i][2])
            else:
                anss.append(Qer[i][2])
        else:
            if Qer[i][1] =="2":
                anss.appendleft(Qer[i][2])
            else:
                anss.append(Qer[i][2])
anss=''.join(anss)
if flag == True:
    print(anss)
else:
    anss = anss[::-1]
    print(anss)
### BUGGY CODE ###

isprimes = [True]*(10**5+1)
isprimes[0] = False
isprimes[1] = False
for i in range(2, 10**5+1):
  if isprimes[i]:
    j = i**2
    while j < 10**5+1:
      isprimes[j] = False
      j += i
Q = int(input())
for _ in range(Q):
  c = 0
  l, r = map(int, input().split())
  for x in range(l, r+1, 2):
    if isprimes[x] and isprimes[(x+1)//2]:
      c += 1
  print(c)


### FIXED CODE ###

isprimes = [True]*(10**5+1)
isprimes[0] = False
isprimes[1] = False
for i in range(2, 10**5+1):
  if isprimes[i]:
    j = i**2
    while j < 10**5+1:
      isprimes[j] = False
      j += i
islikes = [False]*(10**5+1)
for i in range(3, 10**5+1, 2):
  if isprimes[i] and isprimes[(i+1)//2]:
    islikes[i] = True
ruiseki = [0]*(10**5+1)
for i in range(1, 10**5+1):
  ruiseki[i] = ruiseki[i-1]+(1 if islikes[i] else 0)
Q = int(input())
for _ in range(Q):
  l, r = map(int, input().split())
  print(ruiseki[r]-ruiseki[l-1])
### BUGGY CODE ###

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

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

ans=0
for i in range(N):
    for j in range(i+1, N):
        if cs[i] == cs[j]:
            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 ###

N = int(input())
data = [int(i) for i in input().split()]
Q = int(input())

array = dict()
for i in data:
  if i in array:
    array[i] += 1
  else:
    array[i] = 1
    
for i in range(Q):
  quary = [int(i) for i in input().split()]
  if quary[0] not in array:
    pass
  elif quary[1] in array:
    array[quary[1]] += array[quary[0]]
    del array[quary[0]]
  else:
    array[quary[1]] = array[quary[0]]
    del array[quary[0]]
  
  total = 0
  for i, j in array.items():
    total += i*j
  print(total)

### FIXED CODE ###

N = int(input())
data = [int(i) for i in input().split()]
Q = int(input())

array = dict()
for i in data:
  if i in array:
    array[i] += 1
  else:
    array[i] = 1
    
total = 0
for i, j in array.items():
  total += i*j
  
for i in range(Q):
  dt = 0
  quary = [int(i) for i in input().split()]
  if quary[0] not in array:
    pass
  elif quary[1] in array:
    dt = (quary[1]-quary[0])*array[quary[0]]
    array[quary[1]] += array[quary[0]]
    del array[quary[0]]
  else:
    dt = (quary[1]-quary[0])*array[quary[0]]
    array[quary[1]] = array[quary[0]]
    del array[quary[0]]
  
  total += dt
  print(total)
### BUGGY CODE ###

def D_joisino_travel(N, M, R, r, A):
    """
    N:国の中の町の数
    M:町を結ぶ道の総数
    R:訪れる町の数
    r:訪れる町の番号
    A:町の結び方とその間の距離
    """
    from itertools import permutations
    INF = float('inf')
    # 道の番号-1が要素の番号
    r = [x - 1 for x in r]
    dist = [[INF]*N for j in range(N)]
    for i in range(N):
        dist[i][i] = 0
    for m, n, c in A:
        m-=1
        n-=1
        dist[m][n] = c
        dist[n][m] = c

    # ワーシャルフロイド法(町A→Bの最短距離を求められる)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    permutation_route = permutations(r)
    min_dist = INF
    for i in permutation_route:
        cost = 0
        for j in range(R - 1):  # i(行く町の順列)の先頭から2つ要素を拾う
            cost += dist[i[j]][i[j + 1]]  # コストはワーシャルフロイド法で求めてある
        min_dist = min(min_dist, cost)
    return min_dist
  
N,M,R = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(M)]
print(D_joisino_travel(N, M, R, r, A))

### FIXED CODE ###

def D_joisino_travel(N, M, R, r, A):
    """
    N:国の中の町の数
    M:町を結ぶ道の総数
    R:訪れる町の数
    r:訪れる町の番号
    A:町の結び方とその間の距離
    """
    from itertools import permutations
    INF = float('inf')
    # 道の番号-1が要素の番号
    r = [x - 1 for x in r]
    dist = [[INF]*N for j in range(N)]
    for i in range(N):
        dist[i][i] = 0
    for m, n, c in A:
        m-=1
        n-=1
        dist[m][n] = c
        dist[n][m] = c

    # ワーシャルフロイド法(町A→Bの最短距離を求められる)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    permutation_route = permutations(r)
    min_dist = INF
    for i in permutation_route:
        cost = 0
        for j in range(R - 1):  # i(行く町の順列)の先頭から2つ要素を拾う
            cost += dist[i[j]][i[j + 1]]  # コストはワーシャルフロイド法で求めてある
        min_dist = min(min_dist, cost)
    return min_dist
  
N,M,R = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(M)]
print(D_joisino_travel(N, M, R, r, A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    K = input().replace("\n", "")
    D = int(input())
    
    mod = pow(10, 9)+7
    n = len(K)
    dp = [[0]*D for _ in range(n+1)]
    
    dp[0][0] = 1
    sub = 0
    
    if D == 1:
        ans = 0
        for i in range(n):
            ans = (ans*10+int(K[i]))%mod
        print(ans)
        sys.exit()


    for i in range(n):
        if i != 0:
            for j in range(10):
                for k in range(D):
                    dp[i+1][(k+j)%D] += dp[i][k]
                    dp[i+1][(k+j)%D] %= mod
            for j in range(1, 10):
                dp[i+1][j%D] += 1
                dp[i+1][j%D] %= mod
        
        
        for j in range(int(K[i])):
            if i == 0 and j == 0:
                continue
            dp[i+1][(j+sub)%D] += 1
            dp[i+1][(j+sub)%D] %= mod
        sub = (sub+int(K[i]))%D
    
    sub = 0
    for i in range(n):
        sub = (sub+int(K[i]))%D
    if sub == 0:
        dp[n][0] += 1
        dp[n][0] %= mod
        
    
    print(dp[n][0])
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    K = input().replace("\n", "")
    D = int(input())
    
    mod = pow(10, 9)+7
    n = len(K)
    dp = [[0]*D for _ in range(n+1)]
    
    dp[0][0] = 1
    sub = 0
    
    if D == 1:
        ans = 0
        for i in range(n):
            ans = (ans*10+int(K[i]))%mod
        print(ans)
        sys.exit()


    for i in range(n):
        if i != 0:
            for j in range(10):
                for k in range(D):
                    dp[i+1][(k+j)%D] += dp[i][k]
                    dp[i+1][(k+j)%D] %= mod
            for j in range(1, 10):
                dp[i+1][j%D] += 1
                dp[i+1][j%D] %= mod
        
        
        for j in range(int(K[i])):
            if i == 0 and j == 0:
                continue
            dp[i+1][(j+sub)%D] += 1
            dp[i+1][(j+sub)%D] %= mod
        sub = (sub+int(K[i]))%D
    
    sub = 0
    for i in range(n):
        sub = (sub+int(K[i]))%D
    if sub == 0:
        dp[n][0] += 1
        dp[n][0] %= mod
        
    
    print(dp[n][0])
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

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

g = set(i for i in range(1,N+1))
for i in range(M):
    l,r = map(int, input().split())
    t = set(i for i in range(l,r+1))
    g = g & t

print(len(g))


### FIXED CODE ###

import sys
input=sys.stdin.readline

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

l,r = 1,N
for i in range(M):
    l1,r1 = map(int, input().split())
    if l1>l:
        l = l1
    if r1<r:
        r = r1
if r-l<0:
    print(0)
else:
    print(r-l+1)
### BUGGY CODE ###

import heapq
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())))[::-1]
C = [(-A[i]*F[i], F[i], A[i]) for i in range(N)]
heapq.heapify(C)
x1, y1, z1 = heapq.heappop(C)
while z1 > 0 and K > 0:
    #print(x1, y1)
    x2, y2, z2 = heapq.heappop(C)
    a = min((x2 - x1)//z1 + 1, K, z1)
    K -= a
    heapq.heappush(C, (x1 + a*y1, y1, z1 - a))
    x1, y1, z1 = x2, y2, z2
    #print(y2)
print(- x1)

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted(list(map(int, input().split())), reverse=True))

left = - 1
right = 10**12

def f(x):
    return np.maximum(0, A - x//F) .sum()<= K

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)
### BUGGY CODE ###

from math import sqrt
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = set(A)
B = dict(Counter(A))
ans = 0
for i in range(N):
    if B[A[i]] > 1:
        pass
    else:
        flag = True
        for j in range(1, A[i]+1):
            if j**2 > A[i]:
                break
            if A[i] % j == 0:
                if A[i]//j in C:
                    if A[i]//j < A[i]:
                        flag = False
                        break
                if j in C:
                    if j < A[i]:
                        flag = False
                        break

        ans += int(flag)
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
visited=[False for i in range(10**6+1)]
ban=[False for i in range(10**6+1)]
from collections import Counter
A.sort()
D=dict(Counter(A))
for n in A:
    if visited[n]==False:
        visited[n]=True
        for j in range(2,10**6):
            if 10**6<n*j:
                break 
            ban[n*j]=True
ans=0
for n in A:
    if D[n]==1 and ban[n]==False:
        ans+=1
print(ans)
### BUGGY CODE ###

n,w = map(int, input().split())
max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = map(int, input().split())
    for j in range(1, weight):
        max_value[i][j] = max_value[i-1][j]
    for j in range(weight, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i-1][j-weight] + value)

print(max_value[n][w])

### FIXED CODE ###

n,w = map(int, input().split())
max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = map(int, input().split())
    for j in range(1, weight):
        max_value[i][j] = max_value[i-1][j]
    for j in range(weight, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i-1][j-weight] + value)

print(max_value[n][w])
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
rmax = N // R
gmax = N // G
bmax = N // B
ans = 0
for r in range(rmax+1):
    for g in range(gmax+1):
        if (N - (R*r + G*g)) % B == 0 and 0 <= (N - (R*r + G*g) )// B <= bmax: 
            ans += 1
print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
rmax = N // R
gmax = N // G
bmax = N // B
ans = 0
for r in range(rmax+1):
    for g in range(gmax+1):
        if (N - (R*r + G*g)) % B == 0 and 0 <= (N - (R*r + G*g) )// B <= bmax: 
            ans += 1
print(ans)
### BUGGY CODE ###

A, B = map(int, input().split())
ans = A
for i in range(A+1, B+1):
    ans = ans ^ i
print(ans)


### FIXED CODE ###

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


def xor(n):
    m = 0
    if n % 4 == 0:
        m = n
    elif n % 4 == 1:
        m = 1
    elif n % 4 == 2:
        m = n + 1
    return m


p = xor(A-1)
q = xor(B)
print(p ^ q)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
def main():
    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    c = 1
    ma = 0
    for i, (amax, amin) in enumerate(zip(A[k - 1:], reversed(A[:n - k + 1])), k - 1):
        ma = (ma + c * (amax - amin)) % MOD
        c = c * (i + 1) // (i - k + 2)
    print(ma)

main()


### FIXED CODE ###

MOD = 10 ** 9 + 7

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = MOD
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

def prep(n):
    for i in range(2, n):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)


def main():
    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    c = 1
    ma = 0
    prep(n)
    for i, (amax, amin) in enumerate(zip(A[k - 1:], reversed(A[:n - k + 1])), k - 1):
        ma = (ma + cmb(i, k - 1, MOD) * (amax - amin)) % MOD
    print(ma)

main()
### BUGGY CODE ###

l,r=map(int,open(0).read().split())

if r-l>=2019:
    print(0)

m=[]
for i in range(l,r+1):
    m.append(i%2019)

n=len(m)
ans=2019

for i in range(n):
    for j in range(i+1,n):
        ans=min(ans,(m[i]*m[j])%2019)
    
print(ans)

### FIXED CODE ###

l,r=map(int,open(0).read().split())

if r-l>=2019:
    print(0)
    exit(0)

m=[]
for i in range(l,r+1):
    m.append(i%2019)

n=len(m)
ans=2019

for i in range(n):
    for j in range(i+1,n):
        ans=min(ans,(m[i]*m[j])%2019)
    
print(ans)