ankit-and-race-team-10

Coach Ankit is forming a team for the Annual Inter Galactic Relay Race. He has N students that train under him and he knows their strengths. The strength of a student is represented by a positive integer.

The coach has to form a team of K students. The strength of a team is defined by the strength of the weakest student in the team. Now he wants to know the sum of strengths of all the teams of size K that can be formed modulo 1000000007. Please help him.

Input
The first line contains the number of test cases T.
Each case begins with a line containing integers N and K. The next line contains N space-separated numbers which describe the strengths of the students.

Output
For test case output a single integer, the answer as described in the problem statement.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 100000
1 ≤ K ≤ N
0 ≤ Strength of each student ≤ 2000000000
Strength of all the students are different.

SAMPLE INPUT
2
2 1
5 4
3 2
1 0 2

SAMPLE OUTPUT
9
1

Explanation

For first test case: 5+4=9, as team can only consist of 1 student.
For second test case: min(1,0) + min(1,2) + min(0,2) = 0+1+0 =1

Difficulty: MEDIUM
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
"""
calculate ncr%p where p is prime using inverse modulo

1)nck = n*(n-1)*(n-2)...(n-k+1)
	---------------------- = num/den
	1*2*............k
	
2)nck = num*den^-1

3)nck%p = ((num%p)*(den^-1%p))%p

4)den^-1 = den^(p-2)=den^b

4)nck%p = ((num%p)*(den^b%p))%p


5)we know that (a^b)%c = ((a%c)^b)%c;den^b%p = ((den%p)^b)%p

6)nck%p = ((num%p)*((den%p)^b)%p)%p

7)now calculate num%p and den%p  easily using (a*b)%p = (a%p*b%p)%p

8)after den%p = a has been calculated we compute now (a^b)%p using fast modular exponention

"""



def modpow(a,x,p):
    #calculates a^x mod p in logarithmic time.
    res= 1
    while(x>0):
	if (x%2 ==1):
	    res*=a
	    res%=p
	a = a*a
	a%=p
	x=x/2
    return res
	
def modInverse(a,p):
     #calculates the modular multiplicative of a mod p.
    #(assuming p is prime).
    return modpow(a,p-2,p)



def comp(n,r,fact,ifact,M):
    ret = (fact[n]*ifact[r])%M
    ret *=ifact[n-r]
    ret = ret%M
    return ret
    
    


def precompute(fact,ifact,N,M):
    fact[0] = 1

    for i in range(1,N):
	fact[i] = (i*fact[i-1])%M

    ifact[N-1] = modpow(fact[N-1],M-2,M) 

    j= N-2
    while(j>=0):
	ifact[j]= ((j+1)*ifact[j+1])%M
	j-=1
    
	
N = 100005
M = 1000000007
fact  = [0]*N
ifact = [0]*N
precompute(fact,ifact,N,M)


T = int(input())
for t in range(T):
    n,k = [int(x) for x in input().split()]
   
    strength = [int(x) for x in input().split()]
    strength.sort()
    res = 0
    i=0
    for i in range(n-k+1):
	ncr = comp(n-i-1,k-1,fact,ifact,M)
	ncr = (ncr*strength[i])%M
	res = (res +ncr)%M
    print(res)
	


"""
calculate ncr%p where p is prime using inverse modulo

1)nck = n*(n-1)*(n-2)...(n-k+1)
	---------------------- = num/den
	1*2*............k
	
2)nck = num*den^-1

3)nck%p = ((num%p)*(den^-1%p))%p

4)den^-1 = den^(p-2)=den^b

4)nck%p = ((num%p)*(den^b%p))%p


5)we know that (a^b)%c = ((a%c)^b)%c;den^b%p = ((den%p)^b)%p

6)nck%p = ((num%p)*((den%p)^b)%p)%p

7)now calculate num%p and den%p  easily using (a*b)%p = (a%p*b%p)%p

8)after den%p = a has been calculated we compute now (a^b)%p using fast modular exponention

"""


'''
precompute works as follows
Firstly, we denote the multiplicative inverse of x mod p as inv(x,p).

1) use dp method to calculation x! mod p for x=1 ~ n (1<=n<p, p is some prime)
2) calculate inv(n!,p) utilize Extended Euclidean algorithm. but here we do by by fact that inv(a)%p ,if p is prime then inv(a) = a^p-2
3) use dp again to calculate inv(x!,p) for x=n-1 ~ 1 with the fact inv(x!,p) * x = inv((x-1)!, p)
4) now, if we want to now inv(x,p) for some x in [1,n], we only need to calculate (x-1)! * inv(x!,p)


'''
def modpow(a,x,p):
    #calculates a^x mod p in logarithmic time.
    res= 1
    while(x>0):
	if (x%2 ==1):
	    res*=a
	    res%=p
	a = a*a
	a%=p
	x=x/2
    return res
	
def modInverse(a,p):
     #calculates the modular multiplicative of a mod p.
    #(assuming p is prime).
    return modpow(a,p-2,p)



def comp(n,r,fact,ifact,M):
    ret = (fact[n]*ifact[r])%M
    ret *=ifact[n-r]
    ret = ret%M
    return ret
    
    


def precompute(fact,ifact,N,M):
    fact[0] = 1

    for i in range(1,N):
	fact[i] = (i*fact[i-1])%M

    ifact[N-1] = modInverse(fact[N-1],M) 

    j= N-2
    while(j>=0):
	ifact[j]= ((j+1)*ifact[j+1])%M
	j-=1

    
	
N = 100005
M = 1000000007
fact  = [0]*N
ifact = [0]*N
precompute(fact,ifact,N,M)


T = int(input())
for t in range(T):
    n,k = [int(x) for x in input().split()]
   
    strength = [int(x) for x in input().split()]
    strength.sort()
    res = 0
    i=0
    for i in range(n-k+1):
	ncr = comp(n-i-1,k-1,fact,ifact,M)
	ncr = (ncr*strength[i])%M
	res = (res +ncr)%M
    print(res)
	


"""
calculate ncr%p where p is prime using inverse modulo

1)nck = n*(n-1)*(n-2)...(n-k+1)
	---------------------- = num/den
	1*2*............k
	
2)nck = num*den^-1

3)nck%p = ((num%p)*(den^-1%p))%p

4)den^-1 = den^(p-2)=den^b

4)nck%p = ((num%p)*(den^b%p))%p


5)we know that (a^b)%c = ((a%c)^b)%c;den^b%p = ((den%p)^b)%p

6)nck%p = ((num%p)*((den%p)^b)%p)%p

7)now calculate num%p and den%p  easily using (a*b)%p = (a%p*b%p)%p

8)after den%p = a has been calculated we compute now (a^b)%p using fast modular exponention

"""


'''
precompute works as follows
Firstly, we denote the multiplicative inverse of x mod p as inv(x,p).

1) use dp method to calculation x! mod p for x=1 ~ n (1<=n<p, p is some prime)
2) calculate inv(n!,p) utilize Extended Euclidean algorithm. but here we do by by fact that inv(a)%p ,if p is prime then inv(a) = a^p-2
3) use dp again to calculate inv(x!,p) for x=n-1 ~ 1 with the fact inv(x!,p) * x = inv((x-1)!, p)
4) now, if we want to now inv(x,p) for some x in [1,n], we only need to calculate (x-1)! * inv(x!,p)


'''
def modpow(a,x,p):
    #calculates a^x mod p in logarithmic time.
    res= 1
    while(x>0):
	if (x%2 ==1):
	    res*=a
	    res%=p
	a = a*a
	a%=p
	x=x/2
    return res
	
def modInverse(a,p):
     #calculates the modular multiplicative of a mod p.
    #(assuming p is prime).
    return modpow(a,p-2,p)



def comp(n,r,fact,ifact,M):
    ret = (fact[n]*ifact[r])%M
    ret *=ifact[n-r]
    ret = ret%M
    return ret
    
    


def precompute(fact,ifact,N,M):
    fact[0] = 1

    for i in range(1,N):
	fact[i] = (i*fact[i-1])%M

    ifact[N-1] = modInverse(fact[N-1],M) 

    j= N-2
    while(j>=0):
	ifact[j]= ((j+1)*ifact[j+1])%M
	j-=1

    
	
N = 100005
M = 1000000007
fact  = [0]*N
ifact = [0]*N
precompute(fact,ifact,N,M)


T = int(input())
for t in range(T):
    n,k = [int(x) for x in input().split()]
   
    strength = [int(x) for x in input().split()]
    strength.sort()
    res = 0
    i=0
    for i in range(n-k+1):
	ncr = comp(n-i-1,k-1,fact,ifact,M)
	ncr = (ncr*strength[i])%M
	res = (res +ncr)%M
    print(res)
	


maxN=10**5+30
fact=[1]*maxN
inv=[1]*maxN
MOD=10**9+7

def power(a,b):
	if b==0:
		return 1
	if b%2==0:
		x=power(a,b/2)%MOD
		return (x*x)%MOD
	else:
		x=power(a,b/2)%MOD
		return (a*((x*x)%MOD))%MOD

		
t=int(input())
for i in range(2,maxN):
	fact[i]=(fact[i-1]*i)%MOD
inv[maxN-1]=power(fact[maxN-1],MOD-2)%MOD
for i in range(maxN-1,0,-1):
	inv[i-1]=i*inv[i]%MOD
	


for asdgdsg in range(t):
	n,k=(int(e) for e in input().split())
	arr=[int(e) for e in input().split()]
	s=0
	arr.sort()
	for i in range(0,len(arr)-k+1):
		temp=n-i-1
		temp=fact[temp]
		temp=(((temp*inv[n-i-k])%MOD)*inv[k-1])%MOD
		temp=temp*arr[i]%MOD
		s+=temp
	print(s%MOD)


maxN=10**5+30
fact=[1]*maxN
inv=[1]*maxN
MOD=10**9+7

def power(a,b):
	if b==0:
		return 1
	if b%2==0:
		x=power(a,b/2)%MOD
		return (x*x)%MOD
	else:
		x=power(a,b/2)%MOD
		return (a*((x*x)%MOD))%MOD

		
t=int(input())
for i in range(2,maxN):
	fact[i]=(fact[i-1]*i)%MOD
inv[maxN-1]=power(fact[maxN-1],MOD-2)%MOD
for i in range(maxN-1,0,-1):
	inv[i-1]=i*inv[i]%MOD
	


for asdgdsg in range(t):
	n,k=(int(e) for e in input().split())
	arr=[int(e) for e in input().split()]
	s=0
	arr.sort()
	for i in range(0,len(arr)-k+1):
		temp=n-i-1
		temp=fact[temp]
		temp=(((temp*inv[n-i-k])%MOD)*inv[k-1])%MOD
		temp=temp*arr[i]%MOD
		s+=temp
	print(s%MOD)