#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<int>;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& val) {
  if (!val.empty()) {
    os << val.front();
    for (int i = 1; i < val.size(); ++i) os << ' ' << val[i];
  }
  return os;
}
class vector_hasher {
 public:
  size_t operator()(vector<int> const& vec) const {
    size_t seed = vec.size();
    for (auto& i : vec)
      seed ^= (unsigned int)i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    return seed;
  }
};
const int mod = 998244353;
inline int Add(int x) { return x >= mod ? (x - mod) : x; }
inline void add(int& x, int y) {
  if ((x += y) >= mod) x -= mod;
}
inline void sub(int& x, int y) {
  if ((x -= y) < 0) x += mod;
}
inline void exGcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exGcd(b, a % b, y, x);
  y -= a / b * x;
}
inline int get_inv(int a) {
  int x, y;
  exGcd(a, mod, x, y);
  return Add(x + mod);
}
inline int ksm(int x, int k) {
  int res = 1;
  for (; k; k >>= 1, x = x * (ll)x % mod)
    if (k & 1) res = res * (ll)x % mod;
  return res;
}
int main() {
  int n = read(), k = read(), c = read(), xsum = 0;
  int mult = get_inv((ksm(n, k) * (1LL << c)) % mod);
  vec Inv(k + 1), ifac(k + 1);
  for (int i = 1; i <= k; ++i) Inv[i] = get_inv(i);
  ifac[0] = 1;
  for (int i = 1; i <= k; ++i) ifac[i] = ifac[i - 1] * (ll)Inv[i] % mod;
  unordered_map<vector<int>, int, vector_hasher> mp;
  while (n--) {
    int x = read();
    xsum ^= x;
    vector<int> seq(k);
    for (int i = 1; i <= k; ++i) seq[i - 1] = x ^ (x - i);
    ++mp[seq];
  }
  vector<vec> val(k + 1, vec(1 << c));
  for (const auto& [seq, cnt] : mp) {
    vector<int> basis(c), id(c, -1), col(k);
    int dim = 0;
    auto ins = [&](int x) {
      for (int i = 0; i < c; ++i)
        if ((x >> i) & 1)
          if (basis[i])
            x ^= basis[i];
          else {
            basis[i] = x;
            id[i] = dim++;
            return;
          }
    };
    auto work = [&](int x) {
      int col = 0;
      for (int i = 0; i < c; ++i)
        if ((x >> i) & 1) {
          x ^= basis[i];
          col ^= 1 << id[i];
        }
      return col;
    };
    auto comb = [&](int x) {
      int res = 0;
      for (int i = 0; i < c; ++i)
        if (id[i] != -1)
          if ((x >> id[i]) & 1) res ^= basis[i];
      return res;
    };
    for (int x : seq) ins(x);
    for (int i = 0; i < k; ++i) col[i] = work(seq[i]);
    vector<vec> Ln(k + 1, vec(1 << dim));
    for (int i = 1; i <= k; ++i) {
      for (int s = 0; s != 1 << dim; ++s) {
        ull val = 0;
        for (int j = 1; j <= i; ++j)
          val += Ln[i - j][s ^ col[j - 1]] * (ull)ifac[j];
        Ln[i][s] = Add(mod - int(val % mod));
      }
      add(Ln[i][col[i - 1]], ifac[i - 1]);
    }
    for (int i = 1; i <= k; ++i)
      for (int s = 0; s != 1 << dim; ++s)
        Ln[i][s] = Ln[i][s] * (ull)Inv[i] % mod;
    vector<int> Tmp(1 << dim);
    for (int i = 0; i != 1 << dim; ++i) Tmp[i] = comb(i);
    for (int i = 1; i <= k; ++i)
      for (int s = 0; s != 1 << dim; ++s)
        val[i][Tmp[s]] = (val[i][Tmp[s]] + Ln[i][s] * (ull)cnt) % mod;
  }
  auto FWT = [&](vec& vec) {
    for (int i = 0; i != c; ++i)
      for (int s = 0; s != 1 << c; ++s)
        if ((s >> i) & 1) {
          int a0 = vec[s ^ (1 << i)], a1 = vec[s];
          vec[s ^ (1 << i)] = Add(a0 + a1);
          vec[s] = Add(mod + a0 - a1);
        }
  };
  for (int i = 1; i <= k; ++i) FWT(val[i]);
  vec res(1 << c);
  for (int s = 0; s != 1 << c; ++s) {
    vec f(k + 1), exp(k + 1);
    for (int i = 1; i <= k; ++i) f[i] = val[i][s] * (ull)i % mod;
    exp[0] = 1;
    for (int i = 1; i <= k; ++i) {
      ull val = 0;
      for (int j = 1; j <= i; ++j) val += f[j] * (ull)exp[i - j];
      exp[i] = val % mod * Inv[i] % mod;
    }
    res[s] = exp[k];
  }
  FWT(res);
  for (int i = 1; i <= k; ++i) mult = mult * (ull)i % mod;
  for (int i = 0; i != 1 << c; ++i)
    cout << (res[i ^ xsum] * (ull)mult % mod) << ' ';
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

You are given a positive integer k and an array a_1, a_2, …, a_n of non-negative distinct integers not smaller than k and not greater than 2^c-1.

In each of the next k seconds, one element is chosen randomly equiprobably out of all n elements and decreased by 1.

For each integer x, 0 ≤ x ≤ 2^c - 1, you need to find the probability that in the end the bitwise XOR of all elements of the array is equal to x. 

Each of these values can be represented as an irreducible fraction p/q, and you need to find the value of p ⋅ q^{-1} modulo 998 244 353. 

Input

The first line of input contains three integers n, k, c (1 ≤ n ≤ (2^c - k), 1 ≤ k ≤ 16, 1 ≤ c ≤ 16).

The second line contains n distinct integers a_1, a_2, …, a_n (k ≤ a_i ≤ 2^c-1).

Output

Print 2^c integers: the probability that the bitwise XOR is equal to x in the end for x in \{0, 1, …, 2^c-1\} modulo 998 244 353.

Example

Input


4 1 3
1 2 3 4


Output


0 0 0 748683265 0 499122177 0 748683265 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<int>;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& val) {
  if (!val.empty()) {
    os << val.front();
    for (int i = 1; i < val.size(); ++i) os << ' ' << val[i];
  }
  return os;
}
class vector_hasher {
 public:
  size_t operator()(vector<int> const& vec) const {
    size_t seed = vec.size();
    for (auto& i : vec)
      seed ^= (unsigned int)i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    return seed;
  }
};
const int mod = 998244353;
inline int Add(int x) { return x >= mod ? (x - mod) : x; }
inline void add(int& x, int y) {
  if ((x += y) >= mod) x -= mod;
}
inline void sub(int& x, int y) {
  if ((x -= y) < 0) x += mod;
}
inline void exGcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exGcd(b, a % b, y, x);
  y -= a / b * x;
}
inline int get_inv(int a) {
  int x, y;
  exGcd(a, mod, x, y);
  return Add(x + mod);
}
inline int ksm(int x, int k) {
  int res = 1;
  for (; k; k >>= 1, x = x * (ll)x % mod)
    if (k & 1) res = res * (ll)x % mod;
  return res;
}
int main() {
  int n = read(), k = read(), c = read(), xsum = 0;
  int mult = get_inv((ksm(n, k) * (1LL << c)) % mod);
  vec Inv(k + 1), ifac(k + 1);
  for (int i = 1; i <= k; ++i) Inv[i] = get_inv(i);
  ifac[0] = 1;
  for (int i = 1; i <= k; ++i) ifac[i] = ifac[i - 1] * (ll)Inv[i] % mod;
  unordered_map<vector<int>, int, vector_hasher> mp;
  while (n--) {
    int x = read();
    xsum ^= x;
    vector<int> seq(k);
    for (int i = 1; i <= k; ++i) seq[i - 1] = x ^ (x - i);
    ++mp[seq];
  }
  vector<vec> val(k + 1, vec(1 << c));
  for (const auto& [seq, cnt] : mp) {
    vector<int> basis(c), id(c, -1), col(k);
    int dim = 0;
    auto ins = [&](int x) {
      for (int i = 0; i < c; ++i)
        if ((x >> i) & 1)
          if (basis[i])
            x ^= basis[i];
          else {
            basis[i] = x;
            id[i] = dim++;
            return;
          }
    };
    auto work = [&](int x) {
      int col = 0;
      for (int i = 0; i < c; ++i)
        if ((x >> i) & 1) {
          x ^= basis[i];
          col ^= 1 << id[i];
        }
      return col;
    };
    auto comb = [&](int x) {
      int res = 0;
      for (int i = 0; i < c; ++i)
        if (id[i] != -1)
          if ((x >> id[i]) & 1) res ^= basis[i];
      return res;
    };
    for (int x : seq) ins(x);
    for (int i = 0; i < k; ++i) col[i] = work(seq[i]);
    vector<vec> Ln(k + 1, vec(1 << dim));
    for (int i = 1; i <= k; ++i) {
      for (int s = 0; s != 1 << dim; ++s) {
        ull val = 0;
        for (int j = 1; j <= i; ++j)
          val += Ln[i - j][s ^ col[j - 1]] * (ull)ifac[j];
        Ln[i][s] = Add(mod - int(val % mod));
      }
      add(Ln[i][col[i - 1]], ifac[i - 1]);
    }
    for (int i = 1; i <= k; ++i)
      for (int s = 0; s != 1 << dim; ++s)
        Ln[i][s] = Ln[i][s] * (ull)Inv[i] % mod;
    vector<int> Tmp(1 << dim);
    for (int i = 0; i != 1 << dim; ++i) Tmp[i] = comb(i);
    for (int i = 1; i <= k; ++i)
      for (int s = 0; s != 1 << dim; ++s)
        val[i][Tmp[s]] = (val[i][Tmp[s]] + Ln[i][s] * (ull)cnt) % mod;
  }
  auto FWT = [&](vec& vec) {
    for (int i = 0; i != c; ++i)
      for (int s = 0; s != 1 << c; ++s)
        if ((s >> i) & 1) {
          int a0 = vec[s ^ (1 << i)], a1 = vec[s];
          vec[s ^ (1 << i)] = Add(a0 + a1);
          vec[s] = Add(mod + a0 - a1);
        }
  };
  for (int i = 1; i <= k; ++i) FWT(val[i]);
  vec res(1 << c);
  for (int s = 0; s != 1 << c; ++s) {
    vec f(k + 1), exp(k + 1);
    for (int i = 1; i <= k; ++i) f[i] = val[i][s] * (ull)i % mod;
    exp[0] = 1;
    for (int i = 1; i <= k; ++i) {
      ull val = 0;
      for (int j = 1; j <= i; ++j) val += f[j] * (ull)exp[i - j];
      exp[i] = val % mod * Inv[i] % mod;
    }
    res[s] = exp[k];
  }
  FWT(res);
  for (int i = 1; i <= k; ++i) mult = mult * (ull)i % mod;
  for (int i = 0; i != 1 << c; ++i)
    cout << (res[i ^ xsum] * (ull)mult % mod) << ' ';
  return 0;
}

```