#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int mul(int x, int y) { return (1LL * x * y) % mod; }
int power(int a, int b) {
  int res = 1 % mod;
  while (b) {
    if (b % 2) {
      res = mul(res, a);
    }
    b /= 2;
    a = mul(a, a);
  }
  return res;
}
int inv(int x) { return power(x, mod - 2); }
const int max_f = (1 << 16) + 5;
int f[max_f], rf[max_f];
void get_all_f() {
  f[0] = rf[0] = 1;
  for (int i = 1; i < max_f; ++i) {
    f[i] = mul(i, f[i - 1]);
  }
  rf[max_f - 1] = inv(f[max_f - 1]);
  for (int i = max_f - 2; i > 0; --i) {
    rf[i] = mul(i + 1, rf[i + 1]);
  }
}
int get_c(int n, int k) {
  if (n < k) {
    return 0;
  }
  return mul(f[n], mul(rf[k], rf[n - k]));
}
inline void inc(int &x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}
const int max_mask = (1 << 16), inf = 1000111222;
const int max_pos = 12, small = 16;
const int max_cnt = 17;
int n, k, c, a[max_pos][small];
int to_xor, ans[max_mask], cnt[2][max_cnt][small],
    tmp_ways[2][2][max_cnt][small], tmp[small];
int ways[max_pos][2][max_cnt][small];
int dp1[1 << 6][max_cnt][small];
int dp2[1 << 6][max_cnt][small], tmp_dp[2][max_cnt][small];
vector<vector<pair<int, int>>> all;
void rec(int pos, int need, vector<pair<int, int>> v) {
  if (pos == 17) {
    all.push_back(v);
    return;
  }
  for (int c = 0; c * pos <= need; ++c) {
    if (c) {
      v.push_back({pos, c});
    }
    rec(pos + 1, need - c * pos, v);
    if (c) {
      v.pop_back();
    }
  }
}
void convolve(int *y, int n) {
  if (n == 1) {
    return;
  }
  n /= 2;
  convolve(y, n);
  convolve(y + n, n);
  for (int i = 0; i < n; ++i) {
    int a = y[i];
    int b = y[i + n];
    inc(y[i], b);
    y[i + n] = a;
    inc(y[i + n], mod - b);
  }
}
int tmp_conv[small];
const int rn = inv(small);
void xor_convolution(int a[small], int b[small], int c[small]) {
  copy(a, a + small, tmp_conv);
  convolve(tmp_conv, small);
  copy(b, b + small, c);
  convolve(c, small);
  for (int i = 0; i < small; ++i) {
    c[i] = mul(c[i], tmp_conv[i]);
  }
  convolve(c, small);
  for (int i = 0; i < small; ++i) {
    c[i] = mul(c[i], rn);
  }
}
bool get_bit(int mask, int pos) { return (mask >> pos) & 1; }
void calc_dp(int l, int r, int dp[1 << 6][max_cnt][small]) {
  for (int mask_rev = 0; mask_rev < (1 << (r - l)); ++mask_rev) {
    memset(tmp_dp, 0, sizeof(tmp_dp));
    int q1 = 0, q2 = 1;
    tmp_dp[q1][0][0] = 1;
    for (int i = l; i < r; ++i) {
      memset(tmp_dp[q2], 0, sizeof(tmp_dp[q2]));
      for (int c1 = 0; c1 <= k; ++c1) {
        for (int c2 = 0; c1 + c2 <= k; ++c2) {
          const int coef = get_c(c1 + c2, c1);
          xor_convolution(tmp_dp[q1][c1], ways[i][get_bit(mask_rev, i - l)][c2],
                          tmp);
          for (int mask = 0; mask < small; ++mask) {
            inc(tmp_dp[q2][c1 + c2][mask], mul(coef, tmp[mask]));
          }
        }
      }
      swap(q1, q2);
    }
    for (int c = 0; c <= k; ++c) {
      for (int mask = 0; mask < small; ++mask) {
        dp[mask_rev][c][mask] = tmp_dp[q1][c][mask];
      }
    }
  }
}
int main() {
  get_all_f();
  scanf("%d%d%d", &n, &k, &c);
  rec(1, k, {});
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    to_xor ^= x;
    int cnt = 0;
    if ((x >> 4)) {
      cnt = __builtin_ctz(x >> 4);
    }
    ++a[cnt][x & (small - 1)];
  }
  for (int pos = 0; pos < max_pos; ++pos) {
    int q1 = 0, q2 = 1;
    memset(tmp_ways, 0, sizeof(tmp_ways));
    tmp_ways[q1][0][0][0] = 1;
    for (int mask = 0; mask < small; ++mask) {
      memset(cnt, 0, sizeof(cnt));
      for (const auto &v : all) {
        int elems = 0;
        for (const auto &p : v) {
          elems += p.second;
        }
        if (elems > a[pos][mask]) {
          continue;
        }
        int res = 1;
        int tot = 0, cur = a[pos][mask];
        int res_mask = 0, rev = 0;
        for (const auto &p : v) {
          res = mul(res, get_c(cur, p.second));
          cur -= p.second;
          res = mul(res, power(rf[p.first], p.second));
          tot += p.first * p.second;
          if (p.second % 2) {
            res_mask ^= mask;
            res_mask ^= (mask + small - p.first) & (small - 1);
            if (mask < p.first) {
              rev ^= 1;
            }
          }
        }
        res = mul(res, f[tot]);
        inc(cnt[rev][tot][res_mask], res);
      }
      memset(tmp_ways[q2], 0, sizeof(tmp_ways[q2]));
      for (int cur_rev = 0; cur_rev < 2; ++cur_rev) {
        for (int nxt_rev = 0; nxt_rev < 2; ++nxt_rev) {
          for (int c1 = 0; c1 <= k; ++c1) {
            for (int c2 = 0; c1 + c2 <= k; ++c2) {
              const int coef = get_c(c1 + c2, c1);
              xor_convolution(tmp_ways[q1][cur_rev][c1], cnt[nxt_rev][c2], tmp);
              for (int mask = 0; mask < small; ++mask) {
                inc(tmp_ways[q2][cur_rev ^ nxt_rev][c1 + c2][mask],
                    mul(coef, tmp[mask]));
              }
            }
          }
        }
      }
      swap(q1, q2);
    }
    for (int rev = 0; rev < 2; ++rev) {
      for (int c = 0; c <= k; ++c) {
        for (int mask = 0; mask < small; ++mask) {
          ways[pos][rev][c][mask] = tmp_ways[q1][rev][c][mask];
        }
      }
    }
  }
  calc_dp(0, max_pos / 2, dp1);
  calc_dp(max_pos / 2, max_pos, dp2);
  for (int m1 = 0; m1 < (1 << 6); ++m1) {
    for (int m2 = 0; m2 < (1 << 6); ++m2) {
      const int full = m1 | (m2 << 6);
      int big_mask = 0;
      for (int i = 0; i < max_pos; ++i) {
        if (get_bit(full, i)) {
          big_mask ^= (1 << (i + 1)) - 1;
        }
      }
      big_mask <<= 4;
      for (int c1 = 0; c1 <= k; ++c1) {
        const int c2 = k - c1;
        const int coef = get_c(c1 + c2, c1);
        xor_convolution(dp1[m1][c1], dp2[m2][c2], tmp);
        for (int mask = 0; mask < small; ++mask) {
          inc(ans[to_xor ^ mask ^ big_mask], mul(coef, tmp[mask]));
        }
      }
    }
  }
  int tot = inv(power(n, k));
  for (int i = 0; i < (1 << c); ++i) {
    printf("%d ", mul(ans[i], tot));
  }
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following problem:

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;
const int mod = 998244353;
int mul(int x, int y) { return (1LL * x * y) % mod; }
int power(int a, int b) {
  int res = 1 % mod;
  while (b) {
    if (b % 2) {
      res = mul(res, a);
    }
    b /= 2;
    a = mul(a, a);
  }
  return res;
}
int inv(int x) { return power(x, mod - 2); }
const int max_f = (1 << 16) + 5;
int f[max_f], rf[max_f];
void get_all_f() {
  f[0] = rf[0] = 1;
  for (int i = 1; i < max_f; ++i) {
    f[i] = mul(i, f[i - 1]);
  }
  rf[max_f - 1] = inv(f[max_f - 1]);
  for (int i = max_f - 2; i > 0; --i) {
    rf[i] = mul(i + 1, rf[i + 1]);
  }
}
int get_c(int n, int k) {
  if (n < k) {
    return 0;
  }
  return mul(f[n], mul(rf[k], rf[n - k]));
}
inline void inc(int &x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}
const int max_mask = (1 << 16), inf = 1000111222;
const int max_pos = 12, small = 16;
const int max_cnt = 17;
int n, k, c, a[max_pos][small];
int to_xor, ans[max_mask], cnt[2][max_cnt][small],
    tmp_ways[2][2][max_cnt][small], tmp[small];
int ways[max_pos][2][max_cnt][small];
int dp1[1 << 6][max_cnt][small];
int dp2[1 << 6][max_cnt][small], tmp_dp[2][max_cnt][small];
vector<vector<pair<int, int>>> all;
void rec(int pos, int need, vector<pair<int, int>> v) {
  if (pos == 17) {
    all.push_back(v);
    return;
  }
  for (int c = 0; c * pos <= need; ++c) {
    if (c) {
      v.push_back({pos, c});
    }
    rec(pos + 1, need - c * pos, v);
    if (c) {
      v.pop_back();
    }
  }
}
void convolve(int *y, int n) {
  if (n == 1) {
    return;
  }
  n /= 2;
  convolve(y, n);
  convolve(y + n, n);
  for (int i = 0; i < n; ++i) {
    int a = y[i];
    int b = y[i + n];
    inc(y[i], b);
    y[i + n] = a;
    inc(y[i + n], mod - b);
  }
}
int tmp_conv[small];
const int rn = inv(small);
void xor_convolution(int a[small], int b[small], int c[small]) {
  copy(a, a + small, tmp_conv);
  convolve(tmp_conv, small);
  copy(b, b + small, c);
  convolve(c, small);
  for (int i = 0; i < small; ++i) {
    c[i] = mul(c[i], tmp_conv[i]);
  }
  convolve(c, small);
  for (int i = 0; i < small; ++i) {
    c[i] = mul(c[i], rn);
  }
}
bool get_bit(int mask, int pos) { return (mask >> pos) & 1; }
void calc_dp(int l, int r, int dp[1 << 6][max_cnt][small]) {
  for (int mask_rev = 0; mask_rev < (1 << (r - l)); ++mask_rev) {
    memset(tmp_dp, 0, sizeof(tmp_dp));
    int q1 = 0, q2 = 1;
    tmp_dp[q1][0][0] = 1;
    for (int i = l; i < r; ++i) {
      memset(tmp_dp[q2], 0, sizeof(tmp_dp[q2]));
      for (int c1 = 0; c1 <= k; ++c1) {
        for (int c2 = 0; c1 + c2 <= k; ++c2) {
          const int coef = get_c(c1 + c2, c1);
          xor_convolution(tmp_dp[q1][c1], ways[i][get_bit(mask_rev, i - l)][c2],
                          tmp);
          for (int mask = 0; mask < small; ++mask) {
            inc(tmp_dp[q2][c1 + c2][mask], mul(coef, tmp[mask]));
          }
        }
      }
      swap(q1, q2);
    }
    for (int c = 0; c <= k; ++c) {
      for (int mask = 0; mask < small; ++mask) {
        dp[mask_rev][c][mask] = tmp_dp[q1][c][mask];
      }
    }
  }
}
int main() {
  get_all_f();
  scanf("%d%d%d", &n, &k, &c);
  rec(1, k, {});
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    to_xor ^= x;
    int cnt = 0;
    if ((x >> 4)) {
      cnt = __builtin_ctz(x >> 4);
    }
    ++a[cnt][x & (small - 1)];
  }
  for (int pos = 0; pos < max_pos; ++pos) {
    int q1 = 0, q2 = 1;
    memset(tmp_ways, 0, sizeof(tmp_ways));
    tmp_ways[q1][0][0][0] = 1;
    for (int mask = 0; mask < small; ++mask) {
      memset(cnt, 0, sizeof(cnt));
      for (const auto &v : all) {
        int elems = 0;
        for (const auto &p : v) {
          elems += p.second;
        }
        if (elems > a[pos][mask]) {
          continue;
        }
        int res = 1;
        int tot = 0, cur = a[pos][mask];
        int res_mask = 0, rev = 0;
        for (const auto &p : v) {
          res = mul(res, get_c(cur, p.second));
          cur -= p.second;
          res = mul(res, power(rf[p.first], p.second));
          tot += p.first * p.second;
          if (p.second % 2) {
            res_mask ^= mask;
            res_mask ^= (mask + small - p.first) & (small - 1);
            if (mask < p.first) {
              rev ^= 1;
            }
          }
        }
        res = mul(res, f[tot]);
        inc(cnt[rev][tot][res_mask], res);
      }
      memset(tmp_ways[q2], 0, sizeof(tmp_ways[q2]));
      for (int cur_rev = 0; cur_rev < 2; ++cur_rev) {
        for (int nxt_rev = 0; nxt_rev < 2; ++nxt_rev) {
          for (int c1 = 0; c1 <= k; ++c1) {
            for (int c2 = 0; c1 + c2 <= k; ++c2) {
              const int coef = get_c(c1 + c2, c1);
              xor_convolution(tmp_ways[q1][cur_rev][c1], cnt[nxt_rev][c2], tmp);
              for (int mask = 0; mask < small; ++mask) {
                inc(tmp_ways[q2][cur_rev ^ nxt_rev][c1 + c2][mask],
                    mul(coef, tmp[mask]));
              }
            }
          }
        }
      }
      swap(q1, q2);
    }
    for (int rev = 0; rev < 2; ++rev) {
      for (int c = 0; c <= k; ++c) {
        for (int mask = 0; mask < small; ++mask) {
          ways[pos][rev][c][mask] = tmp_ways[q1][rev][c][mask];
        }
      }
    }
  }
  calc_dp(0, max_pos / 2, dp1);
  calc_dp(max_pos / 2, max_pos, dp2);
  for (int m1 = 0; m1 < (1 << 6); ++m1) {
    for (int m2 = 0; m2 < (1 << 6); ++m2) {
      const int full = m1 | (m2 << 6);
      int big_mask = 0;
      for (int i = 0; i < max_pos; ++i) {
        if (get_bit(full, i)) {
          big_mask ^= (1 << (i + 1)) - 1;
        }
      }
      big_mask <<= 4;
      for (int c1 = 0; c1 <= k; ++c1) {
        const int c2 = k - c1;
        const int coef = get_c(c1 + c2, c1);
        xor_convolution(dp1[m1][c1], dp2[m2][c2], tmp);
        for (int mask = 0; mask < small; ++mask) {
          inc(ans[to_xor ^ mask ^ big_mask], mul(coef, tmp[mask]));
        }
      }
    }
  }
  int tot = inv(power(n, k));
  for (int i = 0; i < (1 << c); ++i) {
    printf("%d ", mul(ans[i], tot));
  }
  return 0;
}

```