记录编号	244181	评测结果	AAAAAAAAAA
题目名称	[COCI 2016] PERICA	最终得分	100
用户昵称	dududu	是否通过	通过
代码语言	C++	运行时间	0.375 s
提交时间	2016-03-31 16:44:23	内存使用	21.68 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define KN 100010
#define LL long long
#define KK 55 
#define P 1000000007
int N,K;
int data[KN];

int C[KN][KK];


void init()
{
	cin>>N>>K;
	
	for(int i=1;i<=N;i++) scanf("%d",&data[i]);
	sort(data+1,data+1+N);
	
	C[0][0]=1;
	for(int i=1;i<=N;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i&&j<=K;j++)
		{
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
		}
	}
}

LL qcheng(LL a,LL b)
{
	LL ans=0;
	
	while(b)
	{
		if(b&1) ans=(a+ans)%P;
		b>>=1;
		a<<=1;
	}
	
	return ans;
}


void solve()
{
	LL ans = 0;
	
	for(int i = 1; i <= N; i++)
		ans=(ans+qcheng((LL)C[i-1][K-1],(LL)data[i]))%P;
	
	printf("%lld\n", ans);
}


void test()
{
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=i&&j<=K;j++)
		cout<<C[i][j]<<" ";
		cout<<endl;
	}
}


void work()
{
	init();
//	test();
	solve();
}

int main()
{
	freopen("perica.in","r",stdin);
	freopen("perica.out","w",stdout);
	work();
	return 0;
}