\(N\) 人の中から \(K\) 人を選び取る方法の数は二項係数 \(C(N,K)\) で表されます。
制約内では \(C(30,15) < 1.6 \times 10^8\) が取りうる最大値なので答えがこの値を超えることはありません。なので、方法の数を \(\bmod{10^9+7}\) で割った余りを取る必要はありません。

\(C(30,15)\) 通りを全探索できればよいのですが、これに \(N\) を掛けた時間計算量 \(O(N \times C(N,K))\) では実行時間制限に間に合いません。

このような場合、 半分全列挙 という手法で全探索を効率化することができることがあります。本問題に沿った形で説明します。

• 人を均等な大きさの \(2\) つの集合 \(X,Y\) に分ける。
• \(X,Y\) それぞれに対し、各人を採用するかしないかの \(2^{|X|}\) および \(2^{|Y|}\) 通りを全探索する。
• 最後に、 \(X,Y\) の適切な組み合わせを全探索する。

各集合に対して、以下を計算します。 ( \(2^{|X|}\) および \(2^{|Y|}\) 通りの全探索です )

• \((\) 選んだ人数 \(k,\) 実力値の総和を \(M\) で割った余り \(s\) \()\) に対する、この条件を満たす人の選び方の方法の数

すると、 \(X\) 側の \((k,s)\) に対し、 \(Y\) 側の \((K-k,(M-s) \bmod{M})\) を組み合わせると問題文中の条件を満たす選び方を抽出できます。

半分全列挙のミソは、愚直に全探索すると時間計算量 \(O(2^{|S|})\) かかる探索を、全探索であるという性質を保ちながら時間計算量 \(O(2^{|S|/2})\) に落とすことができることです。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

map<pi,int> work(int M,vector<int> &A){
  int N=A.size();
  map<pi,int> res;
  for(int i=0;i<(1<<N);i++){
    pi p={0,0};
    for(int j=0;j<N;j++){
      if(i&(1<<j)){
        p.first++;
        p.second+=A[j];
        p.second%=M;
      }
    }
    res[p]++;
  }
  return res;
}

int main(){
  int N,K,M;
  cin >> N >> K >> M;
  vector<int> X,Y;
  for(int i=0;i<N;i++){
    int A;
    cin >> A;
    if(i&1){Y.push_back(A);}
    else{X.push_back(A);}
  }
  auto lef=work(M,X);
  auto rig=work(M,Y);
  int res=0;
  for(auto &nx : lef){
    pi target={K-nx.first.first,(M-nx.first.second)%M};
    auto it=rig.find(target);
    if(it!=rig.end()){
      res+=nx.second*(*it).second;
    }
  }
  cout << res << "\n";
  return 0;
}