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

import re

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = [int(item) for item in re.split(r"\s", input())]

# ACの場所を探す
p_list = [0] * (N - 1)
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list[i] = 1
        i += 2
    else:
        i += 1

out_list = []
for q in range(Q):
    # qに答える
    l_i = l[q] - 1
    r_i = r[q] - 1
    out_list.append(str(sum(p_list[l_i:r_i])))

print("\n".join(out_list))


### FIXED CODE ###

import re
import numpy as np

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = [int(item) for item in re.split(r"\s", input())]

# ACの場所を探す
p_list = [0] * (N + 1)
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list[i + 1] = 1
        i += 2
    else:
        i += 1


cumsum = np.cumsum(p_list)

out_list = []
for q in range(Q):
    # qに答える
    l_i = l[q] - 1
    r_i = r[q] - 1

    if l_i >= 0:
        c_l = cumsum[l_i]
    else:
        c_l = 0
    c_r = cumsum[r_i]
    out_list.append(str(c_r - c_l))

print("\n".join(out_list))
### BUGGY CODE ###

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

res = 1
for i in A:
  res *= i

if res > 10 ** 18:
  print("-1")
else:
  print(res)

### FIXED CODE ###

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

res = 1
if 0 in A:
  print(0)
  exit()
else:
  for i in A:
    res *= i
    if res > 10 ** 18:
      print(-1)
      exit()
print(res)
### BUGGY CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N=int(input())
A=list(map(int,input().split()))
if N==2:
    print(*A)
else:
    A=sorted(A)
    ans1=A[-1]
    del A[-1]
    saidai=ans1/2
    left=0
    right=N-2
    while right-left>1:
        mid=(left+right)//2
        if A[mid]>=saidai:
            right=mid
        else:
            left=mid
    r=combinations_count(ans1,A[right])
    l=combinations_count(ans1,A[left])
    if r>=l:
        print(ans1,A[right])
    else:
        print(ans1,A[left])
        

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
sort_A=sorted(A)
max_A=sort_A[-1]
answer=[]
half_A=max_A//2
number=pow(10,9)
answer=0
for n in range(N-1):
    if number>=abs(sort_A[n]-half_A):
        answer=n
        number=abs(sort_A[n]-half_A)
print(max_A,sort_A[answer])
### BUGGY CODE ###

n,m=map(int,input().split())
s=[]
g=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1:s.append(b)
    elif b==1:s.append(a)
    elif a==n:g.append(b)
    elif b==n:g.append(a)
for i in s:
    if i in g:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

n,m=map(int,input().split())
s=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1 or a==n:s.append(b)
    elif b==1 or b==n:s.append(a)
ls=len(s)
s=list(set(s))
if ls==len(s):print("IMPOSSIBLE")
else:print("POSSIBLE")
### BUGGY CODE ###

import math


def pattern(x, y, z):
    if x == y == z:
        return 1
    elif x != y and y != z and x != z:
        return 6
    else:
        return 3


def check(ans):
    cnt = 0
    for x in range(1, ans):
        if pow(x, 2) > ans:
            break
        for y in range(x, ans):
            if pow(x+y, 2) > ans:
                break
            for z in range(y, ans):
                #tmp = x*(x+y+z) + y*(y+z) + z*z
                tmp = pow(x+y+z, 2) - x*(y+z) - y*z
                if tmp == ans:
                    cnt += pattern(x, y, z)
                elif tmp > ans:
                    break
    print(cnt)


N = int(input())
# x^2 + y^2 + z^2 + x*y + y*z + z*x = n

for i in range(1, N+1):
    #upper_value = int(math.sqrt(i))
    check(i)


### FIXED CODE ###

import math


def pattern(x, y, z):
    if x == y == z:
        return 1
    elif x != y and y != z and x != z:
        return 6
    else:
        return 3


def check(ans):
    cnt = 0
    upper = int(math.sqrt(ans))
    for x in range(1, upper):
        if pow(x, 2) > ans:
            break
        for y in range(x, upper):
            if pow(x+y, 2) > ans:
                break
            for z in range(y, upper):
                tmp = x*(x+y+z) + y*(y+z) + z*z
                # tmp = pow(x+y+z, 2) - x*(y+z) - y*z
                if tmp == ans:
                    cnt += pattern(x, y, z)
                    if x == y and y == z and z == x:
                        print(cnt)
                        return
                elif tmp > ans:
                    break
    print(cnt)


N = int(input())
# x^2 + y^2 + z^2 + x*y + y*z + z*x = n

for i in range(1, N+1):
    # upper_value = int(math.sqrt(i))
    check(i)
### BUGGY CODE ###

import sys
from bisect import insort,bisect_left
input_lines = sys.stdin.readlines()
N,M = map(int,input_lines[0].split())
PY = [list(map(int,input_lines[i+1].split())) for i in range(M)]

d = {}

for py in PY:
    tmp = d.get(py[0],[])
    insort(tmp,py[1])
    d[py[0]] = tmp

for py in PY:
    s1 = str(py[0])
    s1 = ("0"*(6-len(s1)))+s1
    s2 = str(bisect_left(d[py[0]],py[1])+1)
    s2 = ("0"*(6-len(s2)))+s2

    print(s1+s2)


### FIXED CODE ###

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

num = [0]*N
ans = [""]*M

PY.sort(key = lambda x:x[1])

for p,y,i in PY:
    num[p-1] += 1
    ans[i] = str(p).zfill(6) + str(num[p-1]).zfill(6)

for a in ans:
    print(a)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
s = list (set(a))
dp = [True] * (10**6+1)

for x in s:
    e = x*2
    # エラトステネスの篩
    while e <= 10 ** 6:
        dp[e] = False
        e += x

ret = 0
for x in a:
    # 重複なし かつ 素数
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
dp = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    e = x * 2
    while e <= 10 ** 6:
        dp[e] = False
        e += x
ret = 0
for x in a:
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)
### BUGGY CODE ###

N = int(input())

A = []

for _ in range(N):
    A.append(int(input()))

colored = [False] * N
goal = [True] * N

color_num = 0

while colored != goal:
    start = colored.index(False)
    base = A[start]
    colored[start] = True

    for i in range(start+1, N):
        if colored[i] == False:
            if base < A[i] :
                colored[i] = True
                base = A[i]

    color_num += 1

print(color_num)


### FIXED CODE ###

import bisect

N = int(input())

A = [int(input()) for _ in range(N)]

colors = []

for i in range(N-1, -1, -1):
    target = bisect.bisect_right(colors, A[i])

    if target == len(colors):
        colors.append(A[i])
    else:
        colors[target] = A[i]

print(len(colors))
### BUGGY CODE ###

import fractions

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

LCM = A[0]
for i in range(0,N-1,1):
    LCM = LCM*A[i+1]//fractions.gcd(A[i+1],LCM)
B = [0 for i in range(0,N,1)]
for i in range(0,N,1):
    B[i]= (LCM%MOD)*pow(A[i],MOD-2,MOD)%MOD

ans = 0
for i in range(0,N,1):
    ans = (B[i] + ans)%MOD

print(ans)

### FIXED CODE ###

def lcm(X,Y):
    x=X
    y=Y
    if y>x:
        x,y=y,x
    while x%y!=0:
        x,y=y,x%y
    return X*Y//y

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

LCM = A[0]
for i in range(0,N-1,1):
    LCM = lcm(LCM,A[i+1])
B = [0 for i in range(0,N,1)]
for i in range(0,N,1):
    B[i]= (LCM%MOD)*pow(A[i],MOD-2,MOD)%MOD

ans = 0
for i in range(0,N,1):
    ans = (B[i] + ans)%MOD

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

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [[-1]*(W+1) for _ in range(N)]
#DP[depth:0~N-1][0~W] calc()の結果をメモる

#合計pwsumの重さを入れた状態で、
#depth以降の品物を選ぶ場合の最大価値を返す関数
def calc(depth, pwsum):
  #メモ済みだったらメモした値を返す
  dp =  DP[depth][pwsum]
  if dp != -1: return dp
  
  nowWei, nowVal = wv[depth] #今選んでる品物のこと
  if pwsum + nowWei > W:
    #入れると重さ超過なので、入れずに次を考える
    if depth >= N-1:
      #今の品物が最後なら、以降得られる価値は0
      DP[depth][pwsum] = 0
      return 0
    else:
      #次の品物がある場合、今のを入れずに次へいく
      irenai = calc(depth+1, pwsum)
      DP[depth][pwsum] = irenai
      return irenai
  if pwsum + nowWei <= W:
    #入れても大丈夫な場合
    if depth >= N-1:
      #今の品物が最後なら、今の品物しか入れられない
      DP[depth][pwsum] = nowVal
      return nowVal
    else:
      #次の品物がある場合、今のを入れる入れないの2択
      ireru = nowVal + calc(depth+1, pwsum+nowWei)
      irenai = calc(depth+1, pwsum)
      DP[depth][pwsum] = max(ireru, irenai)
      return max(ireru, irenai)
    
print(calc(0, 0))

### FIXED CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [0]*(W+1) #0~W
#各iにつき、残り重さがWの時の最大価値をDPに入れる


#i=N-1までいった時のmax(DP)が答え
for i in range(0, N, 1): #0~N-1
  w, v = wv[i]
  #残りwei(W-DPの2個目の添字)がw未満の場合入れられない
  #入れない場合は変えなければいい
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print(max(DP))
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
S = input()
target = "AC"

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

for i in range(Q):
    l, r = input_list[i][0], input_list[i][1]
    sub_str = S[l - 1 : r]
    print(sub_str.count(target))


### FIXED CODE ###

from itertools import accumulate

N, Q = list(map(int, input().split()))
S = input()
target = "AC"

# ACが来たらカウントする
dp = [0] * N
for i in range(1, N):
    s = S[i - 1] + S[i]
    if s == "AC":
        dp[i] += 1

# 累積和
DP = list(accumulate(dp))

input_list = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    print(DP[r - 1] - DP[l - 1])
### BUGGY CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return (gcd(y, x % y))


ans = 0
k = int(input())

for a in range(1, k+1):
    for b in range(1, k + 1):
        t = gcd(a, b)
        for c in range(1, k + 1):
            ans += gcd(t, c)
print(ans)


### FIXED CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return (gcd(y, x % y))


ans = 0
k = int(input())

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a, b), c)
print(ans)
### BUGGY CODE ###

import math
result = 0
k = int(input())
for a in range(1, k+1) :
    for b in range(1, k+1) :
        for c in range(1, k+1) :
            result += math.gcd(math.gcd(a ,b), c)

print(result)

### FIXED CODE ###

import math
result = 0
k = int(input())
for a in range(1, k+1) :
    for b in range(1, k+1) :
        if math.gcd(a ,b) == 1 :
            result += k
        else :
            for c in range(1, k+1) :
                result += math.gcd(math.gcd(a ,b), c)
print(result)
### BUGGY CODE ###

import sys
from copy import deepcopy

F = sys.stdin
N, K = map(int, F.readline().strip("\n").split())
A = [None] * (N + 1)
A[0] = 0
A_order = {0}
for a in range(N):
    A[a+1] = int(F.readline().strip("\n")) - K + A[a]
    A_order |= {A[a+1]}
maxA = len(A_order)
A_order = list(A_order)
A_order.sort()

compressed_A = dict()
for i in range(maxA):
    compressed_A[A_order[i]] = i

bit = [0] * (maxA + 1)
total_inversion = 0
for a in A:
    b = compressed_A[a] + 1
    while b <= maxA + 1: 
        bit[b - 1] += 1
        b += b & -b

    #total sum
    upper = maxA + 1
    upper_sum = 0
    while upper > 0:
        upper_sum += bit[upper - 1]
        upper -= upper & -upper

    #lower sum
    lower = compressed_A[a] + 1
    lower_sum = 0
    while lower > 0:
        lower_sum += bit[lower - 1]
        lower -= lower & -lower

    total_inversion += upper_sum - lower_sum
 
print(N * (N + 1) // 2 - total_inversion)

### FIXED CODE ###

import sys
from copy import deepcopy

F = sys.stdin
N, K = map(int, F.readline().strip("\n").split())
A = [None] * (N + 1)
A[0] = 0
A_order = {0}
for a in range(N):
    A[a+1] = int(F.readline().strip("\n")) - K + A[a]
    A_order |= {A[a+1]}
maxA = len(A_order)
A_order = list(A_order)
A_order.sort()

compressed_A = dict()
for i in range(maxA):
    compressed_A[A_order[i]] = i

bit = [0] * (maxA + 1)
total_inversion = 0
for i in range(N+1):
    b = compressed_A[A[i]] + 1
    while b <= maxA + 1: 
        bit[b - 1] += 1
        b += b & -b

    #lower sum
    lower = compressed_A[A[i]] + 1
    lower_sum = 0
    while lower > 0:
        lower_sum += bit[lower - 1]
        lower -= lower & -lower

    total_inversion += i + 1 - lower_sum
 
print(N * (N + 1) // 2 - total_inversion)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
A.sort()
num=[False for _ in range(max(A)+1)]
check=[False for _ in range(max(A)+1)]
for a in A:
    if num[a]:
        check[a]=True
    else:
        num[a]=True
    
for a in A:
    if a>int(max(A)**1/2):
        break
    for k in range(2,max(A)//a+1):
        num[a*k]=False

ans=0
for i in range(1,max(A)+1):
    if num[i] and not check[i]:
        ans+=1
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
D=set()
S=set()
for i in range(N):
    if A[i] in S:
        D.add(A[i])
    else:
        S.add(A[i])
M=max(S)
X=[1 for i in range(M+1)]
for a in S:
    if a in D:
        X[a]=0
    for i in range(2*a,M+1,a):
        X[i]=0
ans=0
for i in range(N):
    if X[A[i]]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

s = list(input())

rm_count=0
rm_index=[]
while True:
    for i in range(len(s)-1):
        if i in rm_index:
            continue
        if s[i] != s[i+1]:
            rm_count=rm_count+2
            rm_index+=[i,i+1]
            #print("DEBUG: {}, {}, count: {}".format(s[i],s[i+1],rm_count))

    for i in sorted(rm_index, reverse=True):
        s.pop(i)
    rm_index=[]
    if len(set(s)) == 1 or len(s) == 0:
        break
print(rm_count)


### FIXED CODE ###

from collections import Counter
s = list(input())
d = Counter(s).most_common(2)

# 文字列すべてが同じ文字のとき
if len(d) == 1:
    print(0)
else:
    print(min(d[0][1],d[1][1])*2)
### BUGGY CODE ###

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

b = set(a)
c = []
for i in b:
  c.append([i, a.count(i)])

t = []
for j in range(len(c)):
  total = c[j][1]
  
  if c[j][0]-1 in b:
    total += c[j-1][1]
  
  if c[j][0]+1 in b:
    total += c[j+1][1]

  t.append(total)

print(max(t))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0] * (int(1e5)+5)
for i in range(n):
    ans[a[i]-1] += 1
    ans[a[i]] += 1
    ans[a[i]+1] += 1
print(max(ans))
### BUGGY CODE ###

s = int(input())
n = input()
ans = 0
for a in range(s):
    p = n[a]
    for b in range(a+1, s):
        q = n[b]
        if p != q:
            for c in range(b+1, s):
                if (b - a) != (c - b):
                    r = n[c]
                    if p != r and q!= r:
                        ans += 1
print(ans)

### FIXED CODE ###

s = int(input())
n = input()
ans = 0
r_set = set()
g_set = set()
b_set = set()

for _ in range(s):
    if n[_] == 'R':
        r_set.add(_)
    elif n[_] == 'G':
        g_set.add(_)
    else:
        b_set.add(_)

len_b = len(b_set)

for r in r_set:
    for g in g_set:
        diff = abs(r - g)
        minus = set()
        if r < g:
            if g + diff in b_set:
                minus.add(g+diff)
            if r - diff in b_set:
                minus.add(r-diff)
        else:
            if r + diff in b_set:
                minus.add(r+diff)
            if g - diff in b_set:
                minus.add(g-diff)
        if (r + g) / 2 in b_set:
            minus.add((r+g)/2)
        ans += len_b - len(minus)

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

import bisect
N, Q = (int(i) for i in input().split())
char = input()
charlist = list(char)
hoge = 0
onon = []
for i in charlist:
    if char[hoge:(hoge + 2)] == "AC":
        onon.append(hoge + 1)
    hoge += 1
    if (hoge - 1) >= int(N):
        break
for i in range(Q):
    l, r = (int(i) for i in input().split())
    result = [i for i in onon if i >= l and i <= (r - 1)]
    left = bisect.bisect_left(onon,l)
    right = bisect.bisect_left(onon,r)
    print(right - left)

### FIXED CODE ###

import bisect
N, Q = (int(i) for i in input().split())
char = input()
charlist = list(char)
hoge = 0
onon = []
for i in charlist:
    if char[hoge:(hoge + 2)] == "AC":
        onon.append(hoge + 1)
    hoge += 1
    if (hoge - 1) >= int(N):
        break
for i in range(Q):
    l, r = (int(i) for i in input().split())
    left = bisect.bisect_left(onon,l)
    right = bisect.bisect_left(onon,r)
    print(right - left)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc084/tasks/abc084_d

Nmax = 10**6 + 1

def prime_test(n):
    i = 2
    while i*i<=n:
        if n%i:
            i += 1
        else:
            return False
    if n == 1:
        return False
    return True

cum = [0]*Nmax

for n in range(1,Nmax,2):
    cum[n] = cum[n-2] + (prime_test(n) and prime_test((n + 1)/2))

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(cum[r] - cum[l-2])

### FIXED CODE ###

# https://atcoder.jp/contests/abc084/tasks/abc084_d

Nmax = 10**5 + 1

def prime_test(n):
    if n == 1:
        return False
    i = 2
    while i*i<=n:
        if n%i:
            i += 1
        else:
            return False
    return True

cum = [0]*Nmax

for n in range(1,Nmax,2):
    cum[n] = cum[n-2] + (prime_test(n) and prime_test((n + 1)/2))

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(cum[r] - cum[l-2])
### BUGGY CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    a, b = ns()

    def sosuserch(n):
        sosu = [2]
        for i in range(3, n):
            flg = True
            for s in sosu:
                if i % s == 0:
                    flg = False
                    break
            if flg:
                if a % i == 0 and b % i == 0:
                    sosu.append(i)

        if n < 2:
            sosu = []
        return sosu


    sosu_set = sosuserch(min(a // 2 + 1, b // 2 + 1))

    print(len(sosu_set) + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    a, b = ns()

    g = fractions.gcd(a, b)

    def search(n):
        i = 2
        so = []
        while not(n == 1 or i * i > n):
            while n % i == 0:
                n //= i
                so.append(i)
            i += 1
        if n != 1:
            so.append(n)

        return so

    ans = set(search(g))
    print(len(ans) + 1)


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

n=int(input())
a=[]
for i in range(n):
    d=input()
    a.append("".join(sorted(d)))
#print(a)

count=0
for i in range(n):
    temp=a.pop()
    count+=a.count(temp)
print(count)


### FIXED CODE ###

from collections import Counter
n=int(input())
d=Counter()
ans=0
for i in range(n):
    t=str("".join(sorted(input())))
    if t in d:
        ans+=d[t]
    d[t]+=1
print(ans)
### BUGGY CODE ###

N=int(input())
X=input()

def pop(x): #10進数
    ret=0
    while x>0:
        ret+=x%2
        x//=2
    return ret

def solve(x): #10進数
    ret=0
    while x>0:
        pop_c=pop(x)
        x%=pop_c
        ret+=1
    return ret

mod=X.count("1") #>0
for i in range(N):
    if X[i]=="0":
        tmp="".join([X[:i],"1",X[i+1:]])
        tmp=int(tmp,2)%(mod+1)
        print(solve(tmp)+1)
    else:
        if mod==1:
            print(0)
            continue
        tmp="".join([X[:i],"0",X[i+1:]])
        tmp=int(tmp,2)%(mod-1)
        print(solve(tmp)+1)


### FIXED CODE ###

N=int(input())
X=input()

def pop(x): #10進数
    ret=0
    while x>0:
        ret+=x%2
        x//=2
    return ret

def solve(x): #10進数
    ret=0
    while x>0:
        pop_c=pop(x)
        x%=pop_c
        ret+=1
    return ret

mod=X.count("1") #>0
original_plus=0
original_minus=0
for i in range(N):
    if X[N-1-i]=="1":
        if mod>1:
            original_minus+=pow(2,i,mod-1)
        original_plus+=pow(2,i,mod+1)
original_plus%=mod+1
if mod>1:
    original_minus%=mod-1
for i in range(N):
    if X[i]=="0":
        tmp=original_plus+pow(2,N-1-i,mod+1)
        tmp%=mod+1
        print(solve(tmp)+1)
    else:
        if mod==1:
            print(0)
            continue
        tmp=original_minus-pow(2,N-1-i,mod-1)
        tmp%=mod-1
        print(solve(tmp)+1)
### BUGGY CODE ###

def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    p = int(input())
    A = list(map(int, input().split()))
    # comb(p - 1, i)
    comb = [1] * p
    for i in range(1, p):
        v = comb[i - 1]
        v *= p - i
        v *= mod_inv(i, p)
        comb[i] = v % p
    b = [0] * p
    for k, a in enumerate(A):
        if a == 0:
            continue
        pw = [1] * p  # (- k)**(p - 1 - i)
        for i in range(1, p):
            pw[- (i + 1)] = (pw[- i] * (- k)) % p
        for i in range(p):
            if i == 0:
                b[i] += 1
            b[i] -= comb[i] * pw[i]
            b[i] %= p
    print(' '.join(map(str, b)))            


if __name__ == '__main__':
    main()

### FIXED CODE ###

def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    p = int(input())
    A = list(map(int, input().split()))
    # comb(p - 1, i)
    comb = [1] * p
    for i in range(1, p):
        v = comb[i - 1]
        v *= p - i
        v *= mod_inv(i, p)
        comb[i] = v % p
    b = [0] * p
    for k, a in enumerate(A):
        if a == 0:
            continue
        pw = [1] * p  # (- k)**(p - 1 - i)
        for i in range(1, p):
            pw[- (i + 1)] = (pw[- i] * (- k)) % p
        for i in range(p):
            if i == 0:
                b[i] += 1
            b[i] -= comb[i] * pw[i]
            b[i] %= p
    print(' '.join(map(str, b)))            


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

from scipy.misc import comb
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A = sorted(A)
mod = (10**9)+7
minlist = [0] * N
maxlist = [0] * N
ans = 0
for i in range(N):
    if N - i >= K:
        kari = comb((N - i - 1), K-1, exact=True) % mod
        # print(kari)
        ans += (kari * A[N-i-1]) % mod
        ans -= (kari * A[i]) % mod
        ans = ans % mod
print(ans)


### FIXED CODE ###

from collections import deque
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A = sorted(A)
B = deque()
C = deque()
mod = (10**9)+7
for h in range(N):
    B.append(A[h])
    C.append(A[h])


def cmb(n, r):  # 【Python】組み合わせ(nCr) 計算の高速化より引用
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


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

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


ans = 0
for i in range(N):
    if N - i >= K:
        kari = cmb(N - i - 1, K-1) % mod
        # print(kari)
        ans += (kari * B.pop()) % mod
        ans -= (kari * C.popleft()) % mod
        ans = ans % mod
print(ans)