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

import numpy as np
n = int(input())
a = [int(i) for i in input().split()] 

a = np.array(a)
ls = a

st = int(n/2)
for ind in range(st, 0, -1):
    tmp = list(range(2*ind-1, n, ind))
    s = ls[tmp].sum()%2
    if a[ind-1] == s:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        
print(sum(ls))
ans = np.where(ls==1)[0] + 1
for i in ans:
    print(i)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()] 
ls = a

st = int(n/2)
ans =  [i+st+1 for i, n in enumerate(a[st:]) if n ==1] 
for ind in range(st, 0, -1):
    tmp = [ls[i] for i in range(2*ind-1, n, ind)]
    s = sum(tmp)%2
    if a[ind-1] == s:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        ans.append(ind)
        
print(sum(ls))
print(' '.join(map(str, ans)))
### BUGGY CODE ###

s = input()
K = int(input())

known = set()
from heapq import *
hq = []
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        ss = s[i:j]
        if ss not in known:
            heappush(hq, ss)
            known.add(ss)
for i in range(K-1):
    heappop(hq)
print(heappop(hq))

### FIXED CODE ###

s = input()
K = int(input())

def f(s, K):
    known = set()
    for i in range(len(s)):
        for j in range(min(len(s), i + 5), i, -1):
            ss = s[i:j]
            if ss in known:
                break
            known.add(ss)
    return sorted(known)[K -1]

print(f(s, K))
### BUGGY CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N=int(input())
A=list(map(int,input().split()))
L=[]

for i in range(1,N+1):
	L.append(str(A.index(i)+1))

print(' '.join(L))

### FIXED CODE ###

import sys
import heapq
from collections import deque
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')



N=int(input())
p=list(map(int,input().split()))	
pp=deque(p)
pp.appendleft(0)

q=sorted(range(len(pp)),key=lambda k:pp[k])
qq=deque(q)
qq.popleft()

print(*qq)
### BUGGY CODE ###

N = int(input())
S = [ [],[],[],[],[],[],[],[],[],[] ]
ans = 0
for i in range(N):
  temps = input()
  if(temps not in S[len(temps)-1]):
    ans += 1
    S[len(temps)-1].append(temps)
print(ans)

### FIXED CODE ###

N = int(input())
d = {}
for i in range(N):
  d[input()] = 1
print(len(d))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
dp = [0]*N
for i in range(N-1):
    t = A[i]
    if t > 2 * 10**5:
        continue
    for j in range(i+t, N):
        if j-i == t+A[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
# dp = [0]*N
# for i in range(N-1):
#     t = A[i]
#     if t > 200000:
#         continue
#     for j in range(i+t+1, N):
#         if j-i == t+A[j]:
#             cnt += 1
# print(cnt)

# i<j
# j-i = A[i]+A[j]
# j-A[j] = i+A[i]
# j+A[j] = i-A[i]
MAX = 2*10**5

dpL = [0]*(MAX)
dpR = [0]*(MAX)
for i in range(N):
    num = A[i]
    if num > 200000:
        continue   
    if i+num < MAX:
        dpL[i+num] += 1
    if i >= num:
        dpR[i-num] += 1

for i in range(MAX):
    l = dpL[i]
    r = dpR[i]
    cnt += l*r

print(cnt)
### BUGGY CODE ###

times=10**100
S=input()

start=-1
cycle=-1
list_list=[]

clist=[1]*len(S)
list_list.append(clist)

dic_list={}
for i in range(1,10**100):  
  new_clist=[0]*len(S)
  for j,s in enumerate(S):
    if s=="L":
      new_clist[j-1]+=clist[j]
    elif s=="R":
      new_clist[j+1]+=clist[j]

  clist=new_clist
  list_list.append(clist)
  #print(clist)
  
  if str(clist) in dic_list:
    #print(i,i-dic_list[str(clist)],str(clist))
    start=dic_list[str(clist)]
    cycle=i-dic_list[str(clist)]
    break
  else:
    dic_list[str(clist)]=i
    
#print(start,cycle,list_list[start])
index=((10**100-start)%cycle)+start
ans_list=map(str,list_list[index])
print(" ".join(ans_list))


### FIXED CODE ###

S=input()
ans_list=[0]*len(S)

rmode=True
cnt_R=0
cnt_L=0
border_R=0
border_L=0
for i in range(len(S)):
  if rmode:
    if S[i]=="R":
      cnt_R+=1
    else:
      border_R=i-1
      border_L=i      
      rmode=False
      cnt_L=1
  else:
    if S[i]=="L":
      cnt_L+=1
    else:
      ans_list[border_R]+=(cnt_R+1)//2
      ans_list[border_L]+=cnt_R//2
      ans_list[border_R]+=cnt_L//2
      ans_list[border_L]+=(cnt_L+1)//2
      rmode=True
      cnt_R=1
      cnt_L=0
else:
  ans_list[border_R]+=(cnt_R+1)//2
  ans_list[border_L]+=cnt_R//2
  ans_list[border_R]+=cnt_L//2
  ans_list[border_L]+=(cnt_L+1)//2
  
      
ans_list_str=map(str,ans_list)
print(" ".join(ans_list_str))
### BUGGY CODE ###

import bisect

n = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
ans = 0
L = [0] * n
for i in range(n):
    a = bisect.bisect_left(A, B[i])
    L[i] = a
for i in range(n):
    b = bisect.bisect_left(B, C[i])
    ans += sum(L[:b])
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
ans = 0
L = [0] * n
for i in range(n):
    a = bisect.bisect_left(A, B[i])
    L[i] = a
cum = [0] * (n + 1)
for i in range(n):
    cum[i+1] = cum[i] + L[i]
for i in range(n):
    b = bisect.bisect_left(B, C[i])
    ans += cum[b]
print(ans)
### BUGGY CODE ###

import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
    s = s.replace(".", "0").replace("#", "1")
    s = list(map(int, list(s)))
    ss.append(s)
ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.pop()
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h, next_w] == 1:
                continue
            if dp[next_h, next_w] > dp[now_h, now_w] + 1:
                dp[next_h, next_w] = dp[now_h, now_w] + 1
                que.append((next_h, next_w))
    return dp

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh, sw] == 0:
            dp = find(sh, sw)
            score = np.max(dp[dp != 9999])
            if maximum < score:
                maximum = score

print(maximum)

### FIXED CODE ###

import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
#     s = s.replace(".", "0").replace("#", "1")
#     s = list(map(int, list(s)))
    ss.append(s)
# ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.popleft()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "#":
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))
#             print(que)
    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            if sh > 0 and sh < h - 1 and sw > 0 and sw < w - 1:
                if 0 + (ss[sh + 1][sw] == ".") + (ss[sh - 1][sw] == ".") + (ss[sh][sw + 1] == ".") + (ss[sh][sw - 1] == ".") >= 3:
                    continue
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)
### BUGGY CODE ###

import sys

def binary_search(array, num):
    if array[-1] <= num:
        return -1
    left = -1
    right = len(array)-1
    while right - left > 1:
        mid = int((left + right)/2)
        if array[mid] <= num:
            left = mid
        else:
            right = mid
    return right

a_index = []
b_index = []

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split(" ")))
A.sort()
B = list(map(int, sys.stdin.readline().strip().split(" ")))
B.sort()
C = list(map(int, sys.stdin.readline().strip().split(" ")))
C.sort()

for a in A:
    a_index.append(binary_search(B, a))

    
for b in B:
    b_index.append(binary_search(C, b))

    
res = 0
for a_i in a_index:
    if a_i == -1:
        continue
    for b_i in b_index[a_i:]:
        res += (N - b_i)
print(str(res))



### FIXED CODE ###

import sys
import numpy as np

def binary_search(array, num):
    # numより真に大きいはじめのindex
    if array[-1] <= num:
        return -1
    left = -1
    right = N-1
    while right - left > 1:
        mid = int((left + right)/2)
        if array[mid] <= num:
            left = mid
        else:
            right = mid
    return right

a_index = []
b_index = []

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split(" ")))
A = np.sort(A)
B = list(map(int, sys.stdin.readline().strip().split(" ")))
B = np.sort(B)
C = list(map(int, sys.stdin.readline().strip().split(" ")))
C = np.sort(C)

for a in A:
    a_index.append(binary_search(B, a))
    
for b in B:
    b_index.append(binary_search(C, b))


b_index = list(map(lambda x: N-x if (x != -1) else 0, b_index))

bb = []
tmp = np.sum(b_index)
for i in range(N):
    bb.append(tmp)
    tmp = tmp - b_index[i]

res = 0
for a_i in a_index:
    if a_i == -1:
        continue
    res += bb[a_i]
print(str(res))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def itercomb(n,k):
    _a = 2**k-1
    yield 2**k-1
    while 1:
        _x = _a & -_a
        _y = _a + _x
        _a = (((_a & ~_y) // _x) >> 1) | _y
        if _a >= 2**n: break
        yield _a

MOD=10**9+7
n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

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

for m in range(1,n+1):
    for a in itercomb(n,m):
        #print(a)
        #if bin(a).count("1") != m: continue
        dp[m][a] = sum(dp[m-1][a-2**c] for c in range(n) if 2**c&a != 0 and A[m-1][c]==1)%MOD


print(dp[n][2**n-1])

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

def itercomb(n,k):
    _a = (1<<k)-1
    yield _a
    while 1:
        _x = _a & -_a
        _y = _a + _x
        _a = (((_a & ~_y) // _x) >> 1) | _y
        if _a >= _ALL: break
        yield _a

n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

MOD=10**9+7
_ALL=1<<n
dp = [0]*(_ALL)
dp[0] = 1

for m in range(1,n+1):
    for a in itercomb(n,m):
        for c,i in enumerate(A[m-1]):
            if (1<<c)&a and i:
                dp[a] += dp[a^(1<<c)]
                if dp[a] > MOD:
                    dp[a] -= MOD


#print(dp)
print(dp[2**n-1])
### BUGGY CODE ###

n=int(input())
s=[]
for i in range(n):
  s.append(sorted(input()))
ans=0
for i in range(n):
  for j in range(n):
    if i>j:
      if s[i]==s[j]:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
slist={}
for i in range(n):
  s=''.join(sorted(input()))
  if s in slist:
    ans+=slist[s]
    slist[s]+=1
  else:
    slist[s]=1

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

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x):
    return pow(x, MOD-2, MOD)

def nPk(n,k):
    x=1
    for a in range(n-k+1, n+1):
        x = x * a % MOD
    return x

def nCk(n,k):
    return nPk(n,k) * inv(nPk(k,k))

MOD = 10**9+7

n,k = get_nums_l()

if k >= n-1:
    print(nCk(n+n-1, n) % MOD)
    exit()

# 0人の部屋=zがk以下であるような人数の並べ方の個数

# z=0 1
# z=1 nC1 * (n-1)**1
# z=2 nC2 * (n-2)**2
# z=3 nC3 * (n-3)**3

ans = 1
for z in range(1,k+1):
    ans += nCk(n,z) * nCk(n-1, z) % MOD

print(ans%MOD)

### FIXED CODE ###

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x):
    return pow(x, MOD-2, MOD)

def nPk(n,k):
    
    # x=1
    # for a in range(n-k+1, n+1):
    #     x = x * a % MOD
    # return x
    return kaijo[n] * inv(kaijo[n-k]) % MOD

def nCk(n,k):
    return nPk(n,k) * inv(kaijo[k])

MOD = 10**9+7

kaijo = [0] * 400020
kaijo[0] = 1
for i in range(1, len(kaijo)):
    kaijo[i] = kaijo[i-1] * i % MOD

n,k = get_nums_l()

if k >= n-1:
    print(nCk(n+n-1, n) % MOD)
    exit()

# 0人の部屋=zがk以下であるような人数の並べ方の個数

# z=0 1
# z=1 nC1 * (n-1)**1
# z=2 nC2 * (n-2)**2
# z=3 nC3 * (n-3)**3

ans = 1
for z in range(1,k+1):
    ans += nCk(n,z) * nCk(n-1, z)

print(ans%MOD)
### BUGGY CODE ###

n,k=map(int,input().split())
L=[[] for i in range(n+1)]

for i in range(n-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    
C=[k for i in range(n+1)]
V=[0 for i in range(n+1)]
mod=1_000_000_007
ans=1
que=[1]
V[1]=1
head=0

while len(que)>head:
    now=que[head]
    head+=1
    ans=ans*C[now]%mod
    for nex in L[now]:
        if V[nex]==0:
            V[nex]=1
            que.append(nex)
        for nexnex in L[nex]:
            C[nexnex]-=1
        C[nex]-=1

print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
L=[[] for i in range(n+1)]

for i in range(n-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    
C=[k for i in range(n+1)]
V=[0 for i in range(n+1)]
mod=1_000_000_007
ans=1
que=[(1,0)]
V[1]=1
head=0

cnt=1
while len(que)>head:
    now=que[head]
    head+=1
    ans=ans*(k-now[1])%mod
    for i in range(len(L[now[0]])):
        nex=L[now[0]][i]
        if V[nex]==0:
            V[nex]=1
            que.append((nex,cnt))
            cnt+=1
    cnt=2

#ans=ans*pow(k-1,mod-2,mod)*k%mod
print(ans)
### BUGGY CODE ###

n = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        b = L[j]
        k = j + 1
        cnt = 0
        while k <= n - 1:
            if L[k] >= a + b:
                break
            k += 1
            cnt += 1
        ans += cnt
print(ans)


### FIXED CODE ###

import bisect

n = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(n):
    a = L[i]
    for j in range(i+1, n):
        b = L[j]
        k = bisect.bisect_left(L, a+b)
        if k > j:
            ans += k - j - 1
print(ans)
### BUGGY CODE ###

n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]

# 横軸：スタート
# 縦軸：ゴール
cumulative_lr = [[0 for x in range(n + 1)] for y in range(n + 1)]
for l, r in lr_array:
    for i in range(1, l+1):
        for j in range(r, n + 1):
            cumulative_lr[i][j] += 1

for p, q in pq_array:
    print(cumulative_lr[p][q])


### FIXED CODE ###

n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]


def solve1():
    table = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        table[l][r] += 1
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = table[i][j - 1] + table[i][j]
    for p, q in pq_array:
        res = 0
        for i in range(p, q + 1):
            # print(i)
            res += table[i][q]
        print(res)

    return 0


# 横軸：スタート
# 縦軸：ゴール
# 2次元累積和で解く
def solve2():
    cumulative_lr = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        for i in range(1, l + 1):
            for j in range(r, n + 1):
                cumulative_lr[i][j] += 1

    for p, q in pq_array:
        print(cumulative_lr[p][q])


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

s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [['' for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            if len(dp[i+1][j]) < len(dp[i][j]) or dp[i+1][j] == '':
                dp[i+1][j] = dp[i][j]
        if j+1 <= LENt:
            if len(dp[i][j+1]) < len(dp[i][j]) or dp[i][j+1] == '':
                dp[i][j+1] = dp[i][j]
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+s[i]

print(dp[-1][-1])

### FIXED CODE ###

s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] ==dp[x][y]:
        x = x-1
    elif dp[x][y] == dp[x][y-1]:
        y = y-1
    elif dp[x-1][y-1]+1== dp[x][y]:
        ans =s[x-1] + ans
        x = x-1
        y = y-1
        continue
#     elif dp[x-1][y] == dp[x][y-1]:
#         x = x-1

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

a,b = map(int,input().split())
ans = a
for x in range(a+1,b+1):
    ans = ans ^ x
print(ans)

### FIXED CODE ###

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

ans = 0
length = b-a+1
if a%2 != 0:
    ans = ans^a
if b%2 == 0:
    length -= 1
    ans = ans^b
pair_count= length//2
ans = ans^(pair_count%2)
print(ans)
### BUGGY CODE ###

# ABC144 C
from itertools import combinations
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def factorize(n):
    retlist = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
                retlist.append(i)
    if temp!=1:
        retlist.append(temp)

    if retlist==[]:
        retlist.append(n)

    return retlist

N = ni()

ans = 0
L = []
L = factorize(N)

ans = 10**13

for i in range(1,len(L)+1):
    C = []
    C = list(combinations(L,i))
    for c in C:
        a,b = 1,0
        for j in range(len(c)):
            a *= c[j]
            b = N//a
            ans = min(ans,a-1+b-1)

print(ans)


### FIXED CODE ###

# ABC144 C - Walk on Multiplication Table
import math
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
n = ni()
sqrtn = int(math.sqrt(n))
for i in range(sqrtn, 0, -1):
    if n%i == 0:
        j = n // i
        print(i+j-2)
        break
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

n = int(input())
a = [int(i) for i in input().split()]

k = [0] * 60

for i in a:
    for j in range(60):
        if (i >> j) & 1:
            k[j] += 1

ans = 0
c = 0
for d in k:
    ans += d * (n - d) * 2**c
    c += 1
    
print(ans % (10**9 + 7))

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import numpy as np

n = int(input())
a = np.array([int(i) for i in input().split()])

k = [0] * 60

for j in range(60):
    l = a & 1
    k[j] = np.count_nonzero(l)
    a >>= 1

ans = 0
c = 0
for d in k:
    ans += (d * (n - d) * 2**c)  % (10**9 + 7)
    c += 1
    
print(ans % (10**9 + 7))
### BUGGY CODE ###

# -*- Coding: utf-8 -*-

x = int(input())
min_sosu = x
flg_found = False

for i in range(x, 1000000):
    for j in range(2, 100000):
        if i%j == 0 and j < x:
            break
        if i%j == 0 and j >= x and i == j:
            min_sosu = i
            flg_found = True
            print(min_sosu)
            break
    if flg_found:
        break


### FIXED CODE ###

# -*- Coding: utf-8 -*-

x = int(input())
min_sosu = x
flg_found = False

for i in range(x, 1000000):
    for j in range(2, i*i):
        if i%j == 0 and j < x:
            break
        if i%j == 0 and j >= x and i == j:
            min_sosu = i
            flg_found = True
            print(min_sosu)
            break
    if flg_found:
        break
### BUGGY CODE ###

if __name__ == '__main__':
    def comb(n, k):
        a = n * (n - 1)
        return a // 2
    n = int(input())
    a = list(map(int, input().split()))
    count = {}
    for i in a:
        count[i] = count.get(i, 0) + 1

    for i in a:
        ans = 0
        for k, v in count.items():
            if k == i:
                ans += comb(v - 1, 2)
            else:
                ans += comb(v, 2)
        print(ans)



### FIXED CODE ###

if __name__ == '__main__':
    def comb(n, k):
        a = n * (n - 1)
        return a // 2
    n = int(input())
    a = list(map(int, input().split()))

    count = {}
    # 10 ** 5
    for i in a:
        count[i] = count.get(i, 0) + 1

    all_sum = 0
    # 10 ** 5
    for i in count.values():
        all_sum += comb(i, 2)

    # 10 ** 5
    for i in a:
        ans = all_sum - comb(count[i], 2) + comb(count[i] - 1, 2)
        print(ans)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()
def comb(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

maxi = 0
for i in range(K-1,N):
    maxi += A[i]*comb(i,K-1)

mini = 0
A.sort(reverse=True)
for j in range(K-1,N):
    mini += A[j]*comb(j,K-1)

print((maxi-mini)%(10**9 + 7))


### FIXED CODE ###

import math
N, K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

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 = 10**9+7 #出力の制限
Ne = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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



maxi = 0
for i in range(K-1,N):
    maxi += A[i]*cmb(i, K-1, mod)

mini = 0
A.sort(reverse=True)
for j in range(K-1,N):
    mini += A[j]*cmb(j, K-1, mod)

print((maxi-mini)%mod)