#include "bits/stdc++.h" 
using namespace std;
 
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define FOR(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
 
using namespace std;
 
typedef long long ll;
 
const int NON_PRIME = 17;
const int MAXMAKS = (1 << NON_PRIME) + 2;
const int MAXN = 100;
const int MAXK = 28;
const int mod = (int) 1e9 + 7;
 
 int arrmask = 0;
 int commask = 0;
int T, n, K, L, a[MAXN];
int result[MAXMAKS][50];
int C[MAXN][MAXN], GCD[MAXN][MAXN];
int isImportant[MAXN];
vector < int > imp;
int closed[1 << 20];
 
inline void precompute() {
  for (int n = 0; n < MAXN; n++) {
    C[n][0] = 1;
  }
  for (int n = 1; n < MAXN; n++) {
    for (int r = 1; r < MAXN; r++) {
      C[n][r] = (C[n - 1][r - 1] + C[n - 1][r]) % mod;
    }
  }
  for (int i = 1; i < MAXN; i++) {
    for (int j = 1; j < MAXN; j++) {
      GCD[i][j] = __gcd(i, j);
    }
  }
}
 
inline int prime(int n) {
  if (n < 2) return false;
  for (int i = 2; i * i <= n; i++) if (n % i == 0) return false;
  return true;
}
 
int present[28], overallPresent[28];
int isRequired[28];
int idx[50], rev[50]; 

 
inline int computeOldRequiredOtherWay(int mask) {
     int elem = commask;
     for(int i = 0; i < (imp.size()); i++){
        if(mask & (1 << i))
            elem |= (1 << (idx[i] - 1));
     }
     mask = 0;
     for(int i = 0; i < L; i++){
        if(elem & (1 << i))
            mask |= (1 << rev[i + 1]);
     }
     int exc = closed[mask] ^ elem;
     int aaa = 0;
     for(int i = 0; i < (imp.size()); i++){
        if(exc & (1 << i)){
            if(!(arrmask & (1 << i))) aaa |= (1 << i);
        }
     }
     return aaa;
}
 
inline void doit(int mask) {
  int req = computeOldRequiredOtherWay(mask);
  for (int i = 0; i < L; i++){
    if(req & (1 << i))
        if (isImportant[i + 1]) return;
  }
  int sz = __builtin_popcount(req);
  for (int k = sz; k <= K; k++) {
    int remK = k - sz;
    int total = L - (int) imp.size();
    int ans = C[remK + total - 1][total - 1];
    result[mask][k] = ans;
  }
}
 
inline int count() {
  int ans = 0;
  if ((int) imp.size() == 0) ans = result[0][K];
  else {
    int anotherAns = 0;
    anotherAns += result[0][K];
    if (anotherAns >= mod) anotherAns -= mod;
    FOR(mask, 1, (1 << imp.size())) FOR(x, 1, K + 1) {
      int cnt = __builtin_popcount(mask);
      // a_1 + a_2 + .. + a_cnt = x - cnt
      if (x < cnt) continue;
      int ways = C[x - 1][cnt - 1];
      anotherAns = (anotherAns + (ways * (long long) result[mask][K - x])) % mod;
    }
    ans = anotherAns;
  }
  return ans;
}
 
inline int solve() {
  memset(result, 0, sizeof(result));
  REP(mask, (1 << imp.size())) doit(mask);
  return count();
}
 
inline void computeImportantElements() {
  memset(isImportant, 0, sizeof(isImportant));
  memset(idx, 0, sizeof idx);
  memset(rev, 0, sizeof rev);
  int ii = 0;
  imp.clear();
  for (int i = 2; i <= L; i++) {
    if (!prime(i)) {
      imp.push_back(i);
      isImportant[i] = true;
      idx[ii] = i;
      rev[i] = ii;
      ii += 1;
    }
  }
}
 
inline void readInput() {
  arrmask = 0;
  cin >> n >> K >> L;
  commask = 0;
  computeImportantElements();
  REP(i, n){
    cin >> a[i];  
    arrmask |= (1 << (a[i] - 1));
    if(isImportant[a[i]]) commask |= (1 << (a[i] - 1));
  }
}

inline void pre(){
    memset(closed, 0, sizeof closed);
    for(int mask = 1; mask < (1 << imp.size()); mask++){
        int low_bit = -1;
        for(int i = 0; i < (int) imp.size(); i++){
            if(mask & (1 << i)){
                low_bit = i;
                break;
            }
        }
        int elements = 0;
        for(int i = 0; i < (int) imp.size(); i++){
            if(mask & (1 << i))
                elements |= (1 << (idx[i] - 1));
        }
        closed[mask] = closed[mask ^ (1 << low_bit)];
        for(int i = low_bit; i < (int) (imp.size()); i++){
            if(mask & (1 << i)){
                int pos = GCD[idx[low_bit]][idx[i]];
                closed[mask] |= (1 << (pos - 1));
            }
        }
        assert((elements & closed[mask]) == elements);
    }
}
 
int main() {
  precompute();
  cin >> T;
  while (T--) { 
    readInput();
    pre(); 
    cout << solve() << '\n';
  }
}