#include <bits/stdc++.h>

#define int int64_t
using namespace std;

const int m = 1000000009;

int inv(int a) {
	return a <= 1 ? a : m - (long long)(m/a) * inv(m % a) % m;
}

signed main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int n,k;
	cin>>n>>k;
	vector<int> v(n);
	vector<int> fact(n+1,1);
	for(int i=1; i<=n; ++i) fact[i]=i*fact[i-1]%m;

	for(auto &i:v) cin>>i;
	sort(v.begin(),v.end());
	
	int ans = 0;

	int lv=-1,ln=0;
	for(int i=0; i<k; ++i) {
		if(v[i]!=lv) ln=0;
		lv=v[i];
		ln++;
		ans-=v[i];
	}

	int rv=-1, rn=0;
	for(int i=n-1; i>=n-k; --i) {
		if(v[i]!=rv) rn=0;
		rv=v[i];
		rn++;
		ans+=v[i];
	}

	int nlv=0,nrv=0;
	for(int i=0; i<n; ++i) {
		nlv+=(v[i]==lv);
		nrv+=(v[i]==rv);
	}

	if(lv==rv) {
		nrv-=ln;
	}
	int cl = fact[nlv]*inv(fact[ln])%m*inv(fact[nlv-ln])%m;
	int cr = fact[nrv]*inv(fact[rn])%m*inv(fact[nrv-rn])%m;

	int cnt = cl*cr%m;

	if(v[0]==v[n-1]) cnt = cnt*inv(2)%m;

	cerr<<ln<<' '<<rn<<' '<<nlv<<' '<<nrv<<' '<<cl<<' '<<cr<<endl;

	cout<<ans<<' '<<cnt<<endl;

	return 0;
}