观察发现，肯定是1个或两个最优。
#include<bits/stdc++.h> #define ll long long #define ull unsigned ll #define uint unsigned #define db long double #define pii pair<int,int> #define pll pair<ll,ll> #define IT iterator #define PB push_back #define MK make_pair #define LB lower_bound #define UB upper_bound #define EB emplace_back #define fi first #define se second #define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++) #define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--) #define UPD(x,y) (((x)+=(y))>=mo?x-=mo:233) #define CLR(a,v) memset(a,v,sizeof(a)); #define CPY(a,b) memcpy(a,b,sizeof(a)); #define LS3 k*2,l,mid #define RS3 k*2+1,mid+1,r #define LS5 k*2,l,mid,x,y #define RS5 k*2+1,mid+1,r,x,y #define GET pushdown(k);int mid=(l+r)/2 #define INF ((1ll<<60)-233) #define sqr(x) ((x)*(x)) #define debug puts("wzpkking") using namespace std; const int mo=1000000007; const int N=(1<<22)+5; int f[N],cnt[N],n,m,k,ans; int power(int x,int y){ int s=1; for (;y;y/=2,x=1ll*x*x%mo) if (y&1) s=1ll*s*x%mo; return s; } int main(){ scanf("%d%d%d",&n,&m,&k); for (int i=1,x;i<=m;i++) scanf("%d",&x),f[x]++; For(i,0,(1<<n)-1) cnt[i]=cnt[i>>1]+(i&1); For(i,0,n-1) For(j,0,(1<<n)-1) if (j&(1<<i)) f[j-(1<<i)]+=f[j]; For(i,1,(1<<n)-1) if (cnt[i]&1) ans=(ans+power(f[i],k))%mo; else ans=(ans-power(f[i],k)+mo)%mo; printf("%d",ans); }