从 @1kri 老师的博客中找来的趣题。博主很有眼光啊！

题意是将 个数划分成 个非空集合，最大化集合内按位与的和，并求出达到最大的方案数。

首先考虑最优化，这种位操作最优化容易想到考察最高位的情况，设当前考虑到第 位，共有 个 ， 个 。

下文只说明 的情况， 稍微改动一点即可。

如果 ，那划分方法中，这些第 位为 的数肯定会单独划到一个集合中去。因为如果让这些 和其余 放在一起，那么虽然低位上的部分有可能变大，但少一个 的代价是低位无论怎么大都补不回来的。于是我们把这 个数单独提出，该位为 的数继续考察下一位即可。

如果 ，那么所有该位为 的数都要划到一个集合中，要不然这 个集合中就会出现至少两个在这一位为 ，也是显然不优的。于是我们把 个数变成了 个数，继续考察下一位即可。

容易发现在位数 时，上述过程都只有一种进行方式，所以只有在 的时候才需要计数。

如果此时 ，那方案数就是把 个数放到 个集合里的方案数 ，否则方案数是把 个数放到 个集合里的方案数 。

于是这题就做完了，时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5,P = 1e9 + 7;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n,k,a[N],fac[N],ifac[N];
inline int qpow(int a,int b) { int res = 1;while(b) { if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
inline void init(int n) {
	fac[0] = 1;
	for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[n] = qpow(fac[n],P - 2);
	for(int i = n - 1;i >= 0;i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
}
inline int C(int n,int m) { if(n < 0 || m < 0 || n < m) return 0; return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
inline int Strling(int n,int m) {
	int res = 0;
	for(int i = 0;i <= m;i++)
		if(i & 1) Plus(res,P - 1ll * C(m,i) * qpow(m - i,n) % P);
		else Plus(res,1ll * C(m,i) * qpow(m - i,n) % P);
	return 1ll * res * ifac[m] % P;
}
long long ans;
int Cnt = 1;
void Solve(vector<int> A,int k,int dep) {
	assert(k <= A.size());
	int cnt0 = 0,cnt1 = 0;
	for(auto i : A) if((i >> dep) & 1) ++cnt1; else ++cnt0;
	ans += min(k - (cnt0 > 0),cnt1) * (1ll << dep);
	if(dep == 0) {
		if(k > cnt1) Cnt = 1ll * Cnt * Strling(cnt0,k - cnt1) % P;
		else Cnt = 1ll * Cnt * Strling(1 + cnt1,k) % P;
		return;
	}
	if(k > cnt1) {
		vector<int> B;
		for(auto i : A) if((~i >> dep) & 1) B.push_back(i); else ans += i & ((1 << dep) - 1);
		Solve(B,k - cnt1,dep - 1);
	} else {
		vector<int> B;int andsum = INT_MAX;
		for(auto i : A) if((i >> dep) & 1) B.push_back(i); else andsum &= i;
		if(cnt0) B.push_back(andsum);
		Solve(B,k,dep - 1);
	}
}
int main() {
	cin >> n >> k;
	for(int i = 1;i <= n;i++) cin >> a[i];
	init(n);
	vector<int> all(a + 1,a + n + 1);
	Solve(all,k,30);
	Cnt = 1ll * Cnt * fac[k] % P;
	printf("%lld %d\n",ans,Cnt);
	return 0;
}