#include <bits/stdc++.h>
using namespace std;
std::mt19937 rnd(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXBIT = 16;
const int MAXDEC = 16;
const int MOD = 998244353;
const int INV2 = (MOD + 1) / 2;
void inc(int& a, int b) {
  if ((a += b) >= MOD) a -= MOD;
}
void dec(int& a, int b) { inc(a, MOD - b); }
int neg(int a) { return a == 0 ? 0 : MOD - a; }
int pw(int x, int n) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % MOD;
    if ((n >>= 1) == 0) return ret;
    x = (long long)x * x % MOD;
  }
}
struct Res {
  int cnt;
  vector<vector<int>> ways;
  vector<vector<int>> trans;
};
int nval, ndec, nbit;
int val[1 << MAXBIT];
int ans[1 << MAXBIT];
bool have[1 << MAXBIT];
int inv[MAXDEC + 1];
int fac[MAXDEC + 1];
int ifac[MAXDEC + 1];
void wht(int* a, int nbits) {
  for (int bit = (0); bit < (nbits); ++bit)
    for (int off = 0; off < (1 << nbits); off += 2 << bit)
      for (int i = (0); i < (1 << bit); ++i) {
        int x = a[off + i], y = a[off + (1 << bit) + i];
        a[off + i] = a[off + (1 << bit) + i] = x;
        inc(a[off + i], y);
        dec(a[off + (1 << bit) + i], y);
      }
}
void verify(const Res& a, int k, char* reason) {
  assert(((int)(a.ways).size()) == ((int)(a.trans).size()));
  for (int i = (0); i < (((int)(a.trans).size())); ++i) {
    assert(((int)(a.ways[i]).size()) == ((int)(a.trans[i]).size()));
    vector<int> tmp = a.trans[i];
    wht(tmp.data(), k);
    int mlt = 1;
    for (int j = (0); j < (k); ++j) mlt = (long long)mlt * INV2 % MOD;
    for (int j = (0); j < (((int)(tmp).size())); ++j)
      tmp[j] = (long long)tmp[j] * mlt % MOD;
    bool ok = true;
    for (int j = (0); j < (((int)(tmp).size())); ++j)
      if (tmp[j] != a.ways[i][j]) ok = false;
    if (!ok)
      printf("err %s!\n", reason);
    else
      printf(".");
  }
}
Res extend(const Res& a, bool toggle) {
  int sz = ((int)(a.trans[0]).size());
  Res ret;
  ret.cnt = a.cnt;
  ret.trans =
      vector<vector<int>>(((int)(a.trans).size()), vector<int>(2 * sz, 0));
  for (int i = (0); i < (((int)(a.trans).size())); ++i)
    for (int j = (0); j < (sz); ++j)
      ret.trans[i][j] = a.trans[i][j],
      ret.trans[i][j + sz] = (!toggle ? +a.trans[i][j] : neg(a.trans[i][j]));
  return ret;
}
const long long MODUNDOOVERFLOW = (1ULL << 63) / MOD * MOD;
Res merge(Res& a, Res& b, int k) {
  int lim = min(((int)(a.trans).size()) + ((int)(b.trans).size()) - 2, ndec),
      sz = ((int)(a.trans[0]).size());
  assert(sz == (1 << (k - 1)));
  Res ret;
  ret.cnt = a.cnt + b.cnt;
  ret.trans = vector<vector<int>>(lim + 1, vector<int>(sz, 0));
  vector<vector<long long>> tmp(lim + 1, vector<long long>(sz, 0));
  for (int i = (0); i < (((int)(a.trans).size())); ++i)
    for (int j = (0); j < (((int)(b.trans).size())); ++j)
      if (i + j <= lim)
        for (int z = (0); z < (sz); ++z) {
          tmp[i + j][z] += (long long)a.trans[i][z] * b.trans[j][z];
          if (tmp[i + j][z] < 0) tmp[i + j][z] -= MODUNDOOVERFLOW;
        }
  for (int i = (0); i <= (lim); ++i)
    for (int z = (0); z < (sz); ++z) ret.trans[i][z] = tmp[i][z] % MOD;
  return ret;
}
Res rec(int k, int offset) {
  if (k == 0) {
    Res ret;
    ret.cnt = 0;
    ret.trans = vector<vector<int>>(1, vector<int>(1, 1));
    return ret;
  } else {
    Res a = rec(k - 1, offset);
    Res b = rec(k - 1, offset + (1 << (k - 1)));
    if (k != 1) a = extend(a, false);
    if (k != 1) b = extend(b, b.cnt % 2 == 1);
    Res ret = merge(a, b, k);
    int lo = max(offset + (1 << (k - 1)), offset + ndec),
        hi = min(offset + (1 << k) - 1, offset + (1 << (k - 1)) + ndec - 1);
    for (int v = (lo); v <= (hi); ++v)
      if (have[v]) {
        Res c;
        c.cnt = 1;
        c.trans = vector<vector<int>>(ndec + 1, vector<int>(1 << (k - 1), 0));
        vector<int> bc(1 << (k - 1), 0);
        for (int i = (1); i < (1 << (k - 1)); ++i) bc[i] = bc[i >> 1] + (i & 1);
        for (int i = (0); i <= (ndec); ++i) {
          int x = ((v - i) & ((1 << k) - 1)) >> 1, y = ifac[i];
          for (int j = (0); j < (1 << (k - 1)); ++j)
            c.trans[i][j] = bc[j & x] % 2 == 0 ? y : neg(y);
        };
        ret = merge(ret, c, k);
      }
    return ret;
  }
}
void solve() {
  inv[1] = 1;
  for (int i = (2); i <= (ndec); ++i)
    inv[i] = (long long)(MOD - MOD / i) * inv[MOD % i] % MOD;
  fac[0] = 1;
  for (int i = (1); i <= (ndec); ++i) fac[i] = (long long)fac[i - 1] * i % MOD;
  ifac[0] = 1;
  for (int i = (1); i <= (ndec); ++i)
    ifac[i] = (long long)ifac[i - 1] * inv[i] % MOD;
  for (int i = (0); i < (1 << nbit); ++i) have[i] = false;
  for (int i = (0); i < (nval); ++i) {
    assert(!have[val[i]]);
    have[val[i]] = true;
  }
  auto res = rec(nbit, 0);
  assert(res.cnt == nval);
  assert(((int)(res.trans).size()) == ndec + 1);
  assert(((int)(res.trans[ndec]).size()) == 1 << (nbit - 1));
  vector<int> tmp = res.trans[ndec];
  wht(tmp.data(), nbit - 1);
  int tot = 1;
  for (int i = (0); i < (ndec); ++i) tot = (long long)tot * nval % MOD;
  int den = pw(tot, MOD - 2);
  int mlt = (long long)fac[ndec] * den % MOD;
  for (int i = (0); i < (nbit - 1); ++i) mlt = (long long)mlt * INV2 % MOD;
  for (int i = (0); i < (1 << nbit); ++i) ans[i] = 0;
  int par = 0;
  for (int i = (0); i < (nval); ++i)
    if (val[i] & 1) par ^= 1;
  if (ndec & 1) par ^= 1;
  for (int i = (0); i < (1 << (nbit - 1)); ++i)
    ans[(i << 1) ^ par] = (long long)tmp[i] * mlt % MOD;
}
void run() {
  scanf("%d%d%d", &nval, &ndec, &nbit);
  for (int i = (0); i < (nval); ++i) scanf("%d", &val[i]);
  solve();
  for (int i = (0); i < (1 << nbit); ++i) {
    if (i != 0) printf(" ");
    printf("%d", ans[i]);
  }
  puts("");
}
void stresstime() {
  for (int rep = (0); rep < (1); ++rep) {
    nbit = MAXBIT, ndec = MAXDEC, nval = (1 << nbit) - ndec;
    for (int i = (0); i < (nval); ++i) val[i] = ndec + i;
    solve();
    printf(".");
  }
}
int main() {
  run();
  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;
std::mt19937 rnd(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXBIT = 16;
const int MAXDEC = 16;
const int MOD = 998244353;
const int INV2 = (MOD + 1) / 2;
void inc(int& a, int b) {
  if ((a += b) >= MOD) a -= MOD;
}
void dec(int& a, int b) { inc(a, MOD - b); }
int neg(int a) { return a == 0 ? 0 : MOD - a; }
int pw(int x, int n) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % MOD;
    if ((n >>= 1) == 0) return ret;
    x = (long long)x * x % MOD;
  }
}
struct Res {
  int cnt;
  vector<vector<int>> ways;
  vector<vector<int>> trans;
};
int nval, ndec, nbit;
int val[1 << MAXBIT];
int ans[1 << MAXBIT];
bool have[1 << MAXBIT];
int inv[MAXDEC + 1];
int fac[MAXDEC + 1];
int ifac[MAXDEC + 1];
void wht(int* a, int nbits) {
  for (int bit = (0); bit < (nbits); ++bit)
    for (int off = 0; off < (1 << nbits); off += 2 << bit)
      for (int i = (0); i < (1 << bit); ++i) {
        int x = a[off + i], y = a[off + (1 << bit) + i];
        a[off + i] = a[off + (1 << bit) + i] = x;
        inc(a[off + i], y);
        dec(a[off + (1 << bit) + i], y);
      }
}
void verify(const Res& a, int k, char* reason) {
  assert(((int)(a.ways).size()) == ((int)(a.trans).size()));
  for (int i = (0); i < (((int)(a.trans).size())); ++i) {
    assert(((int)(a.ways[i]).size()) == ((int)(a.trans[i]).size()));
    vector<int> tmp = a.trans[i];
    wht(tmp.data(), k);
    int mlt = 1;
    for (int j = (0); j < (k); ++j) mlt = (long long)mlt * INV2 % MOD;
    for (int j = (0); j < (((int)(tmp).size())); ++j)
      tmp[j] = (long long)tmp[j] * mlt % MOD;
    bool ok = true;
    for (int j = (0); j < (((int)(tmp).size())); ++j)
      if (tmp[j] != a.ways[i][j]) ok = false;
    if (!ok)
      printf("err %s!\n", reason);
    else
      printf(".");
  }
}
Res extend(const Res& a, bool toggle) {
  int sz = ((int)(a.trans[0]).size());
  Res ret;
  ret.cnt = a.cnt;
  ret.trans =
      vector<vector<int>>(((int)(a.trans).size()), vector<int>(2 * sz, 0));
  for (int i = (0); i < (((int)(a.trans).size())); ++i)
    for (int j = (0); j < (sz); ++j)
      ret.trans[i][j] = a.trans[i][j],
      ret.trans[i][j + sz] = (!toggle ? +a.trans[i][j] : neg(a.trans[i][j]));
  return ret;
}
const long long MODUNDOOVERFLOW = (1ULL << 63) / MOD * MOD;
Res merge(Res& a, Res& b, int k) {
  int lim = min(((int)(a.trans).size()) + ((int)(b.trans).size()) - 2, ndec),
      sz = ((int)(a.trans[0]).size());
  assert(sz == (1 << (k - 1)));
  Res ret;
  ret.cnt = a.cnt + b.cnt;
  ret.trans = vector<vector<int>>(lim + 1, vector<int>(sz, 0));
  vector<vector<long long>> tmp(lim + 1, vector<long long>(sz, 0));
  for (int i = (0); i < (((int)(a.trans).size())); ++i)
    for (int j = (0); j < (((int)(b.trans).size())); ++j)
      if (i + j <= lim)
        for (int z = (0); z < (sz); ++z) {
          tmp[i + j][z] += (long long)a.trans[i][z] * b.trans[j][z];
          if (tmp[i + j][z] < 0) tmp[i + j][z] -= MODUNDOOVERFLOW;
        }
  for (int i = (0); i <= (lim); ++i)
    for (int z = (0); z < (sz); ++z) ret.trans[i][z] = tmp[i][z] % MOD;
  return ret;
}
Res rec(int k, int offset) {
  if (k == 0) {
    Res ret;
    ret.cnt = 0;
    ret.trans = vector<vector<int>>(1, vector<int>(1, 1));
    return ret;
  } else {
    Res a = rec(k - 1, offset);
    Res b = rec(k - 1, offset + (1 << (k - 1)));
    if (k != 1) a = extend(a, false);
    if (k != 1) b = extend(b, b.cnt % 2 == 1);
    Res ret = merge(a, b, k);
    int lo = max(offset + (1 << (k - 1)), offset + ndec),
        hi = min(offset + (1 << k) - 1, offset + (1 << (k - 1)) + ndec - 1);
    for (int v = (lo); v <= (hi); ++v)
      if (have[v]) {
        Res c;
        c.cnt = 1;
        c.trans = vector<vector<int>>(ndec + 1, vector<int>(1 << (k - 1), 0));
        vector<int> bc(1 << (k - 1), 0);
        for (int i = (1); i < (1 << (k - 1)); ++i) bc[i] = bc[i >> 1] + (i & 1);
        for (int i = (0); i <= (ndec); ++i) {
          int x = ((v - i) & ((1 << k) - 1)) >> 1, y = ifac[i];
          for (int j = (0); j < (1 << (k - 1)); ++j)
            c.trans[i][j] = bc[j & x] % 2 == 0 ? y : neg(y);
        };
        ret = merge(ret, c, k);
      }
    return ret;
  }
}
void solve() {
  inv[1] = 1;
  for (int i = (2); i <= (ndec); ++i)
    inv[i] = (long long)(MOD - MOD / i) * inv[MOD % i] % MOD;
  fac[0] = 1;
  for (int i = (1); i <= (ndec); ++i) fac[i] = (long long)fac[i - 1] * i % MOD;
  ifac[0] = 1;
  for (int i = (1); i <= (ndec); ++i)
    ifac[i] = (long long)ifac[i - 1] * inv[i] % MOD;
  for (int i = (0); i < (1 << nbit); ++i) have[i] = false;
  for (int i = (0); i < (nval); ++i) {
    assert(!have[val[i]]);
    have[val[i]] = true;
  }
  auto res = rec(nbit, 0);
  assert(res.cnt == nval);
  assert(((int)(res.trans).size()) == ndec + 1);
  assert(((int)(res.trans[ndec]).size()) == 1 << (nbit - 1));
  vector<int> tmp = res.trans[ndec];
  wht(tmp.data(), nbit - 1);
  int tot = 1;
  for (int i = (0); i < (ndec); ++i) tot = (long long)tot * nval % MOD;
  int den = pw(tot, MOD - 2);
  int mlt = (long long)fac[ndec] * den % MOD;
  for (int i = (0); i < (nbit - 1); ++i) mlt = (long long)mlt * INV2 % MOD;
  for (int i = (0); i < (1 << nbit); ++i) ans[i] = 0;
  int par = 0;
  for (int i = (0); i < (nval); ++i)
    if (val[i] & 1) par ^= 1;
  if (ndec & 1) par ^= 1;
  for (int i = (0); i < (1 << (nbit - 1)); ++i)
    ans[(i << 1) ^ par] = (long long)tmp[i] * mlt % MOD;
}
void run() {
  scanf("%d%d%d", &nval, &ndec, &nbit);
  for (int i = (0); i < (nval); ++i) scanf("%d", &val[i]);
  solve();
  for (int i = (0); i < (1 << nbit); ++i) {
    if (i != 0) printf(" ");
    printf("%d", ans[i]);
  }
  puts("");
}
void stresstime() {
  for (int rep = (0); rep < (1); ++rep) {
    nbit = MAXBIT, ndec = MAXDEC, nval = (1 << nbit) - ndec;
    for (int i = (0); i < (nval); ++i) val[i] = ndec + i;
    solve();
    printf(".");
  }
}
int main() {
  run();
  return 0;
}

```