#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int RangeFind(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcountll(nValue);
}
inline int bitnum(long long nValue) { return __builtin_popcountll(nValue); }
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  if (a == 0) return 0;
  return 64 - __builtin_clzll(a);
}
inline int bitmaxl(long long a) {
  if (a == 0) return 0;
  return 64 - __builtin_clzll(a);
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxbit = 16;
const int maxn = (1 << maxbit) + 10;
const int mod = 998244353;
int orig[maxn];
int cnt[maxbit + 2][maxbit + 2];
long long tdp[maxbit][2][maxbit + 2][maxbit + 2][maxbit];
long long c[maxn][20];
int n, k, bit_max;
long long dp[maxn][maxbit + 2];
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d%d", &n, &k, &bit_max);
  int xor_all = 0;
  for (int i = 0; i < n; i++) {
    scanf("%d", orig + i);
    xor_all ^= orig[i];
    cnt[bitmaxl(lowb(orig[i] >> 4))][orig[i] & 15]++;
  }
  for (int i = 0; i < maxn; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= min(i, maxbit); j++) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
      c[i][j] %= mod;
    }
  }
  for (int suffix_mod = 0; suffix_mod < maxbit; suffix_mod++) {
    memset(tdp[suffix_mod], 0, sizeof(tdp[suffix_mod]));
    tdp[suffix_mod][0][0][0][0] = 1;
    for (int num_cnt = 0; num_cnt < k; num_cnt++) {
      for (int cate = 0; cate < 2; cate++) {
        for (int time_cnt = num_cnt; time_cnt < k; time_cnt++) {
          for (int xor_val = 0; xor_val < maxbit; xor_val++)
            if (tdp[suffix_mod][cate][num_cnt][time_cnt][xor_val]) {
              for (int time_cnt_new = 1; time_cnt_new + time_cnt <= k;
                   time_cnt_new++) {
                const int new_mask =
                    ((suffix_mod + maxbit - time_cnt_new) % maxbit) ^
                    suffix_mod ^ xor_val;
                tdp[suffix_mod][cate ^ (time_cnt_new > suffix_mod)][num_cnt + 1]
                   [time_cnt + time_cnt_new][new_mask] +=
                    tdp[suffix_mod][cate][num_cnt][time_cnt][xor_val] *
                    c[time_cnt + time_cnt_new][time_cnt_new];
                tdp[suffix_mod][cate ^ (time_cnt_new > suffix_mod)][num_cnt + 1]
                   [time_cnt + time_cnt_new][new_mask] %= mod;
              }
            }
        }
      }
    }
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int last_high_bit = 0; last_high_bit <= maxbit - 4; last_high_bit++) {
    long long rdp[2][maxbit + 2][maxbit];
    memset(rdp, 0, sizeof(rdp));
    rdp[0][0][0] = 1;
    for (int suffix_mod = 0; suffix_mod < 16; suffix_mod++)
      if (cnt[last_high_bit][suffix_mod]) {
        for (int time_cnt = k - 1; time_cnt >= 0; time_cnt--)
          for (int cate = 0; cate < 2; cate++)
            for (int xor_val = 0; xor_val < maxbit; xor_val++) {
              if (!rdp[cate][time_cnt][xor_val]) continue;
              for (int rnum_cnt = 1;
                   rnum_cnt <=
                   min(k - time_cnt, cnt[last_high_bit][suffix_mod]);
                   rnum_cnt++) {
                for (int rcate = 0; rcate < 2; rcate++) {
                  for (int rtime_cnt = rnum_cnt; rtime_cnt + time_cnt <= k;
                       rtime_cnt++) {
                    for (int rxor_val = 0; rxor_val < maxbit; rxor_val++)
                      if (tdp[suffix_mod][rcate][rnum_cnt][rtime_cnt]
                             [rxor_val]) {
                        rdp[cate ^ rcate][time_cnt + rtime_cnt]
                           [xor_val ^ rxor_val] +=
                            rdp[cate][time_cnt][xor_val] *
                            tdp[suffix_mod][rcate][rnum_cnt][rtime_cnt]
                               [rxor_val] %
                            mod * c[time_cnt + rtime_cnt][time_cnt] % mod *
                            c[cnt[last_high_bit][suffix_mod]][rnum_cnt];
                        rdp[cate ^ rcate][time_cnt + rtime_cnt]
                           [xor_val ^ rxor_val] %= mod;
                      }
                  }
                }
              }
            }
      }
    for (int rk = k - 1; rk >= 0; rk--)
      for (int last = ((1 << (last_high_bit + 4)) - 1); last >= 0; last--)
        if (dp[last][rk]) {
          for (int rk1 = 1; rk1 + rk <= k; rk1++)
            for (int cate = 0; cate < 2; cate++)
              for (int suffix_mod = 0; suffix_mod < 16; suffix_mod++)
                if (rdp[cate][rk1][suffix_mod]) {
                  dp[last ^ (cate ? ((1 << last_high_bit) - 1) << 4 : 0) ^
                     suffix_mod][rk1 + rk] += dp[last][rk] *
                                              rdp[cate][rk1][suffix_mod] % mod *
                                              c[rk + rk1][rk];
                  dp[last ^ (cate ? ((1 << last_high_bit) - 1) << 4 : 0) ^
                     suffix_mod][rk1 + rk] %= mod;
                }
        }
  }
  long long denom = pow(pow(n, k, mod), mod - 2, mod);
  for (int i = 0; i < (1 << bit_max); i++) {
    printf("%I64d ", dp[i ^ xor_all][k] * denom % mod);
  }
  puts("");
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int RangeFind(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcountll(nValue);
}
inline int bitnum(long long nValue) { return __builtin_popcountll(nValue); }
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  if (a == 0) return 0;
  return 64 - __builtin_clzll(a);
}
inline int bitmaxl(long long a) {
  if (a == 0) return 0;
  return 64 - __builtin_clzll(a);
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxbit = 16;
const int maxn = (1 << maxbit) + 10;
const int mod = 998244353;
int orig[maxn];
int cnt[maxbit + 2][maxbit + 2];
long long tdp[maxbit][2][maxbit + 2][maxbit + 2][maxbit];
long long c[maxn][20];
int n, k, bit_max;
long long dp[maxn][maxbit + 2];
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d%d", &n, &k, &bit_max);
  int xor_all = 0;
  for (int i = 0; i < n; i++) {
    scanf("%d", orig + i);
    xor_all ^= orig[i];
    cnt[bitmaxl(lowb(orig[i] >> 4))][orig[i] & 15]++;
  }
  for (int i = 0; i < maxn; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= min(i, maxbit); j++) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
      c[i][j] %= mod;
    }
  }
  for (int suffix_mod = 0; suffix_mod < maxbit; suffix_mod++) {
    memset(tdp[suffix_mod], 0, sizeof(tdp[suffix_mod]));
    tdp[suffix_mod][0][0][0][0] = 1;
    for (int num_cnt = 0; num_cnt < k; num_cnt++) {
      for (int cate = 0; cate < 2; cate++) {
        for (int time_cnt = num_cnt; time_cnt < k; time_cnt++) {
          for (int xor_val = 0; xor_val < maxbit; xor_val++)
            if (tdp[suffix_mod][cate][num_cnt][time_cnt][xor_val]) {
              for (int time_cnt_new = 1; time_cnt_new + time_cnt <= k;
                   time_cnt_new++) {
                const int new_mask =
                    ((suffix_mod + maxbit - time_cnt_new) % maxbit) ^
                    suffix_mod ^ xor_val;
                tdp[suffix_mod][cate ^ (time_cnt_new > suffix_mod)][num_cnt + 1]
                   [time_cnt + time_cnt_new][new_mask] +=
                    tdp[suffix_mod][cate][num_cnt][time_cnt][xor_val] *
                    c[time_cnt + time_cnt_new][time_cnt_new];
                tdp[suffix_mod][cate ^ (time_cnt_new > suffix_mod)][num_cnt + 1]
                   [time_cnt + time_cnt_new][new_mask] %= mod;
              }
            }
        }
      }
    }
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int last_high_bit = 0; last_high_bit <= maxbit - 4; last_high_bit++) {
    long long rdp[2][maxbit + 2][maxbit];
    memset(rdp, 0, sizeof(rdp));
    rdp[0][0][0] = 1;
    for (int suffix_mod = 0; suffix_mod < 16; suffix_mod++)
      if (cnt[last_high_bit][suffix_mod]) {
        for (int time_cnt = k - 1; time_cnt >= 0; time_cnt--)
          for (int cate = 0; cate < 2; cate++)
            for (int xor_val = 0; xor_val < maxbit; xor_val++) {
              if (!rdp[cate][time_cnt][xor_val]) continue;
              for (int rnum_cnt = 1;
                   rnum_cnt <=
                   min(k - time_cnt, cnt[last_high_bit][suffix_mod]);
                   rnum_cnt++) {
                for (int rcate = 0; rcate < 2; rcate++) {
                  for (int rtime_cnt = rnum_cnt; rtime_cnt + time_cnt <= k;
                       rtime_cnt++) {
                    for (int rxor_val = 0; rxor_val < maxbit; rxor_val++)
                      if (tdp[suffix_mod][rcate][rnum_cnt][rtime_cnt]
                             [rxor_val]) {
                        rdp[cate ^ rcate][time_cnt + rtime_cnt]
                           [xor_val ^ rxor_val] +=
                            rdp[cate][time_cnt][xor_val] *
                            tdp[suffix_mod][rcate][rnum_cnt][rtime_cnt]
                               [rxor_val] %
                            mod * c[time_cnt + rtime_cnt][time_cnt] % mod *
                            c[cnt[last_high_bit][suffix_mod]][rnum_cnt];
                        rdp[cate ^ rcate][time_cnt + rtime_cnt]
                           [xor_val ^ rxor_val] %= mod;
                      }
                  }
                }
              }
            }
      }
    for (int rk = k - 1; rk >= 0; rk--)
      for (int last = ((1 << (last_high_bit + 4)) - 1); last >= 0; last--)
        if (dp[last][rk]) {
          for (int rk1 = 1; rk1 + rk <= k; rk1++)
            for (int cate = 0; cate < 2; cate++)
              for (int suffix_mod = 0; suffix_mod < 16; suffix_mod++)
                if (rdp[cate][rk1][suffix_mod]) {
                  dp[last ^ (cate ? ((1 << last_high_bit) - 1) << 4 : 0) ^
                     suffix_mod][rk1 + rk] += dp[last][rk] *
                                              rdp[cate][rk1][suffix_mod] % mod *
                                              c[rk + rk1][rk];
                  dp[last ^ (cate ? ((1 << last_high_bit) - 1) << 4 : 0) ^
                     suffix_mod][rk1 + rk] %= mod;
                }
        }
  }
  long long denom = pow(pow(n, k, mod), mod - 2, mod);
  for (int i = 0; i < (1 << bit_max); i++) {
    printf("%I64d ", dp[i ^ xor_all][k] * denom % mod);
  }
  puts("");
  return 0;
}

```