#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
using i64 = long long;

class Excavations2 { public: i64 count(vector<int> kind, vector<int> found, int K); };

vector<vector<i64>> nCr;

void init_comb(int n) {
  nCr.assign(n, vector<i64>(n));
  for(int i=0; i<n; i++) { nCr[i][0] = 1; }
  for(int i=1; i<n; i++) for(int j=1; j<n; j++) nCr[i][j] = nCr[i-1][j] + nCr[i-1][j-1];
}

vector<int> cnt, // 昔i番目の種類の建物はcnt[i]個あった。
            found; // 考古学者はfound[i]という種類の建物を発見した。
vector<vector<i64>> dp;

// 考古学者が発見したi番目までのi+1種類でj個の建物が取りうるパターン数を返す。
i64 rec(int i, int j) {
  if(i < 0) { return j==0; } // 考古学者は建物を1種類も発見してない。
  i64 &res = dp[i][j];
  if(res != -1) { return res; }
  int x = cnt[found[i]]; // 考古学者が発見したi番目の種類の建物は昔x個あった。
//  assert(x > 0); // x > 0は保証されている
  res = 0;
  for(int k=1; k<=min(x, j); k++) {
    // 昔x個あったi番目の建物のうちk個発見したときは、
    // 残りのi-1番目までのi種類の建物は全部でj-k個発見した。
    // kは1以上x以下、あるいは1以上j以下。
    // x個からk個を選ぶパターン数はnCr(x, k)。
    res += rec(i-1, j-k) * nCr[x][k]; 
  }
  return res;
}

i64 Excavations2::
count(vector<int> kind, vector<int> _found, int K) {
  found = _found;
  int m = kind.size(), // 昔あった建物の種類数
      n = found.size(); // 考古学者が発見した建物の種類数
  init_comb(51);
  cnt.resize(51);
  for(int i=0; i<m; i++) { cnt[kind[i]]++; }
  dp.assign(n, vector<i64>(51, -1));
  i64 res = rec(n-1, K);
  return res;
}
    

#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
using i64 = long long;

class Excavations2 { public: i64 count(vector<int> kind, vector<int> found, int K); };

vector<vector<i64>> nCr;

void init_comb(int n) {
  nCr.assign(n, vector<i64>(n));
  for(int i=0; i<n; i++) { nCr[i][0] = 1; }
  for(int i=1; i<n; i++) for(int j=1; j<n; j++) nCr[i][j] = nCr[i-1][j] + nCr[i-1][j-1];
}

vector<int> cnt, // 昔i番目の種類の建物はcnt[i]個あった。
            found; // 考古学者はfound[i]という種類の建物を発見した。
vector<vector<i64>> dp;

// 考古学者が発見したi種類j個の建物が取りうるパターン数を返す。
i64 rec(int i, int j) {
  i64 &res = dp[i][j];
  if(res != -1) { return res; }
  if(i == 0) { return res = j==0; } // 考古学者は建物を1種類も発見してない。
  int x = cnt[found[i-1]]; // 考古学者が発見したi種類の建物の最後(=i-1番目)は昔x個あった。
//  assert(x > 0); // x > 0は保証されている
  res = 0;
  for(int k=1; k<=min(x, j); k++) {
    // 昔x個あったi-1番目の建物のうちk個発見したときは、
    // 残りのi-1種類の建物は全部でj-k個発見した。
    // kは1以上x以下、あるいは1以上j以下。
    // x個からk個を選ぶパターン数はnCr(x, k)。
    res += rec(i-1, j-k) * nCr[x][k]; 
  }
  return res;
}

i64 Excavations2::
count(vector<int> kind, vector<int> _found, int K) {
  found = _found;
  int m = kind.size(), // 昔あった建物の種類数
      n = found.size(); // 考古学者が発見した建物の種類数
  init_comb(51);
  cnt.resize(51);
  for(int i=0; i<m; i++) { cnt[kind[i]]++; }
  dp.assign(n+1, vector<i64>(51, -1));
  i64 res = rec(n, K);
  return res;
}
    

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;

class Excavations2 { public: i64 count(vector<int> kind, vector<int> found, int K); };

vector<vector<i64>> nCr;

void init_comb(int n) {
  nCr.assign(n, vector<i64>(n));
  for(int i=0; i<n; i++) { nCr[i][0] = 1; }
  for(int i=1; i<n; i++) for(int j=1; j<n; j++) nCr[i][j] = nCr[i-1][j] + nCr[i-1][j-1];
}

vector<vector<i64>> dp;

i64 Excavations2::
count(vector<int> kind, vector<int> found, int K) {
  int m = kind.size(), 
      n = found.size();
  init_comb(51);
  vector<int> cnt(51);
  for(int i=0; i<m; i++) { cnt[kind[i]]++; }
  dp.assign(n+1, vector<i64>(51, 0));
  dp[0][0] = 1;
  for(int i=0; i<n; i++) {
    for(int j=0; j<K; j++) {
      for(int k=1; k<=K-j; k++) {
        int x = cnt[found[i]];
        dp[i+1][j+k] += dp[i][j] * nCr[x][k];
      }
    }
  }
  i64 res = dp[n][K];
  return res;
}