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 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MODULO = 998244353;
const unsigned long long HALF = ((unsigned long long)1) << 63;
const unsigned long long BIG = HALF - HALF % (unsigned long long)MODULO;
class TaskI {
 public:
  int normalize(int x) {
    int tail = x & 15;
    x >>= 4;
    if (x > 0) {
      int without_last = x & (x - 1);
      int last = x ^ without_last;
      return (last << 4) + tail;
    } else {
      return tail;
    }
  }
  int n, k, c;
  vector<vector<int>> prob;
  vector<vector<unsigned long long>> nprob;
  vector<vector<long long>> comb;
  vector<vector<long long>> tricky;
  map<pair<int, int>, long long> got;
  void update(int a, int count, int taken, int allowed, int xorv,
              long long ways) {
    got[make_pair(taken, xorv)] = (got[make_pair(taken, xorv)] + ways) % MODULO;
    for (int v = min(k - taken, allowed); v >= 1; --v) {
      int nxorv = a ^ (a - v);
      for (int times = 1; times <= count && taken + times * v <= k; ++times) {
        int uxorv = xorv;
        if (times & 1) {
          uxorv ^= nxorv;
        }
        int nways = ways * facts[count] % MODULO * invfacts[times] % MODULO *
                    invfacts[count - times] % MODULO;
        nways = nways * comb[taken + times * v][times * v] % MODULO;
        nways = nways * tricky[times][v] % MODULO;
        update(a, count - times, taken + times * v, v - 1, uxorv, nways);
      }
    }
  }
  vector<long long> invs;
  vector<long long> facts;
  vector<long long> invfacts;
  void solveOne(istream &in, ostream &out) {
    in >> n >> k >> c;
    invs = vector<long long>((1 << c) + 2);
    invs[1] = 1;
    for (int i = 2; i < invs.size(); ++i) {
      invs[i] = ((MODULO - (MODULO / i) * invs[MODULO % i] % MODULO) % MODULO);
    }
    facts = vector<long long>(invs.size());
    invfacts = vector<long long>(invs.size());
    facts[0] = 1;
    invfacts[0] = 1;
    for (int i = 1; i < facts.size(); ++i) {
      facts[i] = (facts[i - 1] * i % MODULO);
      invfacts[i] = (invfacts[i - 1] * invs[i] % MODULO);
    }
    comb = vector<vector<long long>>(k + 1, vector<long long>(k + 1));
    for (int i = 0; i <= k; ++i) {
      for (int j = 0; j <= i; ++j) {
        comb[i][j] = facts[i] * invfacts[j] % MODULO * invfacts[i - j] % MODULO;
      }
    }
    tricky = vector<vector<long long>>(k + 1, vector<long long>(k + 1));
    for (int count = 1; count <= k; ++count) {
      tricky[0][count] = 1;
    }
    for (int slots = 1; slots <= k; ++slots) {
      for (int count = 1; slots * count <= k; ++count) {
        tricky[slots][count] =
            comb[slots * count][count] * tricky[slots - 1][count] % MODULO;
      }
    }
    vector<int> a(n);
    int extra = 0;
    for (int i = 0; i < n; ++i) {
      in >> a[i];
      extra ^= a[i];
      a[i] = normalize(a[i]);
    }
    prob = vector<vector<int>>(k + 1, vector<int>(1 << c));
    nprob = vector<vector<unsigned long long>>(
        k + 1, vector<unsigned long long>(1 << c));
    prob[0][0] = 1;
    sort((a).begin(), (a).end());
    for (int i = 0; i < a.size();) {
      int j = i;
      while (j < a.size() && a[j] == a[i]) ++j;
      int count = j - i;
      got.clear();
      update(a[i], count, 0, k, 0, 1);
      vector<int> maxes(k + 1);
      for (int i = 0; i <= k; ++i) {
        for (int j = 0; j < (1 << c); ++j) {
          if (prob[i][j]) {
            maxes[i] = j + 1;
          }
        }
      }
      for (auto &v : nprob) fill((v).begin(), (v).end(), 0);
      for (int taken = 0; taken <= k; ++taken) {
        for (int old = 0; old + taken <= k; ++old) {
          for (const auto &it : got) {
            if (taken != it.first.first) continue;
            int xorv = it.first.second;
            long long ways = it.second;
            unsigned long long cw = ways * comb[old + taken][taken] % MODULO;
            for (int ov = 0; ov < maxes[old]; ++ov) {
              int nv = ov ^ xorv;
              auto &res = nprob[old + taken][nv];
              res += prob[old][ov] * cw;
              if (res >= HALF) res -= BIG;
            }
          }
        }
      }
      for (int old = 0; old <= k; ++old) {
        for (int ov = 0; ov < (1 << c); ++ov) {
          prob[old][ov] = nprob[old][ov] % MODULO;
        }
      }
      i = j;
    }
    long long denom = 1;
    for (int i = 0; i < k; ++i) {
      denom = denom * invs[n] % MODULO;
    }
    for (int i = 0; i < (1 << c); ++i) {
      int j = i ^ extra;
      long long val = prob[k][j] * denom % MODULO;
      out << val << " ";
    }
    out << "\n";
  }
  void solve(std::istream &in, std::ostream &out) {
    int nt = 1;
    for (int it = 0; it < nt; ++it) {
      solveOne(in, out);
    }
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  TaskI solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}