By the constraints, the number of keys is as small as \(N \le 15\). Also, the tests are also not so many: \(M \le 100\).
Moreover, as described in the problem statement, there are \(2^N\) combinations of authenticities of the keys.

We may perform the \(M\) tests on all the \(2^N\) combinations and count the number of the proper combinations.
Here, \(2^N \times M \le 3.3 \times 10^6\) tests are required. Even if you perform \(N\) operations for a test, the total number of operations is bounded by \(5 \times 10^7\), which is fast enough to be accepted for this problem.

In order to brute-force over the \(2^N\) combinations, bitwise enumeration.

For example, use a for loop that iterates over \(i=0,1,\dots,2^N-1\). If the \(2^k\)s place of \(i\) is \(0\), we assume that the \((k+1)\)-th key is a dummy; if it is \(1\), we assume it a real one. This way, we can exhaustively enumerate all the combinations.

For more details on bitwise enumerations, please refer to the following articles (all in Japanese).

• bit全探索について簡単にまとめる
• こわくないbit全探索1 入門編: bit全探索ってなに？【競プロ解説】
• bit 全探索
• 競技プログラミング講習/bit全探索
• 3.05.ビット演算

Note that spending \(N^2\) operations per test may not fit in the execution time limit.
For example, manage whether the \(k\)-th key was used, just as in the manner of packet sort, to limit the number of operations for a test within \(N\).

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,m,k;
  cin >> n >> m >> k;
  vector<vector<int>> key(m,vector<int>(n,0));
  vector<string> r(m);
  for(int i=0;i<m;i++){
    int c;
    cin >> c;
    for(int j=0;j<c;j++){
      int a;
      cin >> a;
      key[i][a-1]=1;
    }
    cin >> r[i];
  }

  int res=0;
  for(int i=0;i<(1<<n);i++){
    vector<int> tf(n);
    for(int j=0;j<n;j++){
      if(i&(1<<j)){tf[j]=1;}
      else{tf[j]=0;}
    }
    bool jud=true;
    for(int j=0;j<m;j++){
      int ck=0;
      for(int p=0;p<n;p++){
        if(key[j][p]==1 && tf[p]==1){ck++;}
      }
      if(ck>=k && r[j]=="x"){jud=false;}
      if(ck<k && r[j]=="o"){jud=false;}
    }
    if(jud){res++;}
  }
  cout << res << "\n";
  return 0;
}

One can use bitwise operations as follows.
This runs faster than the sample code above.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,m,k;
  cin >> n >> m >> k;
  vector<int> ks(m,0);
  vector<int> r(m,0);
  for(int i=0;i<m;i++){
    int c;
    cin >> c;
    for(int j=0;j<c;j++){
      int a;
      cin >> a;
      a--;
      ks[i]|=(1<<a);
    }
    string s;
    cin >> s;
    if(s=="o"){r[i]=1;}
    else{r[i]=0;}
  }

  int res=0;
  for(int i=0;i<(1<<n);i++){
    bool jud=true;
    for(int j=0;j<m;j++){
      int ok=__builtin_popcount(i&ks[j]);
      if(ok>=k && r[j]==0){jud=false; break;}
      if(ok<k && r[j]==1){jud=false; break;}
    }
    if(jud){res++;}
  }
  cout << res << "\n";
  return 0;
}