Problem: This is the hard version of the problem. The only difference between easy and hard versions is the constraint of m. You can make hacks only if both versions are solved.

Chiori loves dolls and now she is going to decorate her bedroom!

<image>

As a doll collector, Chiori has got n dolls. The i-th doll has a non-negative integer value a_i (a_i < 2^m, m is given). Chiori wants to pick some (maybe zero) dolls for the decoration, so there are 2^n different picking ways.

Let x be the bitwise-xor-sum of values of dolls Chiori picks (in case Chiori picks no dolls x = 0). The value of this picking way is equal to the number of 1-bits in the binary representation of x. More formally, it is also equal to the number of indices 0 ≤ i < m, such that \left⌊ (x)/(2^i) \right⌋ is odd.

Tell her the number of picking ways with value i for each integer i from 0 to m. Due to the answers can be very huge, print them by modulo 998 244 353.

Input

The first line contains two integers n and m (1 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ m ≤ 53) — the number of dolls and the maximum value of the picking way.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i < 2^m) — the values of dolls.

Output

Print m+1 integers p_0, p_1, …, p_m — p_i is equal to the number of picking ways with value i by modulo 998 244 353.

Examples

Input


4 4
3 5 8 14


Output


2 2 6 6 0 

Input


6 7
11 45 14 9 19 81


Output


1 2 11 20 15 10 5 0 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  string sep;
  for (const auto &x : v) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << ' ' << H;
  dbg_out(T...);
}
template <const int &MOD>
struct _m_int {
  int val;
  _m_int(int64_t v = 0) {
    if (v < 0) v = v % MOD + MOD;
    if (v >= MOD) v %= MOD;
    val = v;
  }
  static int inv_mod(int a, int m = MOD) {
    int g = m, r = a, x = 0, y = 1;
    while (r != 0) {
      int q = g / r;
      g %= r;
      swap(g, r);
      x -= q * y;
      swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  explicit operator int() const { return val; }
  explicit operator int64_t() const { return val; }
  _m_int &operator+=(const _m_int &other) {
    val -= MOD - other.val;
    if (val < 0) val += MOD;
    return *this;
  }
  _m_int &operator-=(const _m_int &other) {
    val -= other.val;
    if (val < 0) val += MOD;
    return *this;
  }
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    return x % m;
    unsigned x_high = x >> 32, x_low = (unsigned)x;
    unsigned quot, rem;
    asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
    return rem;
  }
  _m_int &operator*=(const _m_int &other) {
    val = fast_mod((uint64_t)val * other.val);
    return *this;
  }
  _m_int &operator/=(const _m_int &other) { return *this *= other.inv(); }
  friend _m_int operator+(const _m_int &a, const _m_int &b) {
    return _m_int(a) += b;
  }
  friend _m_int operator-(const _m_int &a, const _m_int &b) {
    return _m_int(a) -= b;
  }
  friend _m_int operator*(const _m_int &a, const _m_int &b) {
    return _m_int(a) *= b;
  }
  friend _m_int operator/(const _m_int &a, const _m_int &b) {
    return _m_int(a) /= b;
  }
  _m_int &operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
  _m_int &operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
  _m_int operator++(int) {
    _m_int before = *this;
    ++*this;
    return before;
  }
  _m_int operator--(int) {
    _m_int before = *this;
    --*this;
    return before;
  }
  _m_int operator-() const { return val == 0 ? 0 : MOD - val; }
  bool operator==(const _m_int &other) const { return val == other.val; }
  bool operator!=(const _m_int &other) const { return val != other.val; }
  _m_int inv() const { return inv_mod(val); }
  _m_int pow(int64_t p) const {
    if (p < 0) return inv().pow(-p);
    _m_int a = *this, result = 1;
    while (p > 0) {
      if (p & 1) result *= a;
      a *= a;
      p >>= 1;
    }
    return result;
  }
  friend ostream &operator<<(ostream &os, const _m_int &m) {
    return os << m.val;
  }
};
extern const int MOD = 998244353;
using mod_int = _m_int<MOD>;
const int BITS = 53;
template <typename T>
struct xor_basis {
  T basis[BITS];
  int n = 0;
  T min_value(T start) const {
    if (n == BITS) return 0;
    for (int i = 0; i < n; i++) start = min(start, start ^ basis[i]);
    return start;
  }
  T max_value(T start = 0) const {
    if (n == BITS) return ((T)1 << BITS) - 1;
    for (int i = 0; i < n; i++) start = max(start, start ^ basis[i]);
    return start;
  }
  bool add(T x) {
    x = min_value(x);
    if (x == 0) return false;
    basis[n++] = x;
    for (int k = n - 1; k > 0 && basis[k] > basis[k - 1]; k--)
      swap(basis[k], basis[k - 1]);
    return true;
  }
  void merge(const xor_basis<T> &other) {
    for (int i = 0; i < other.n && n < BITS; i++) add(other.basis[i]);
  }
  void merge(const xor_basis<T> &a, const xor_basis<T> &b) {
    if (a.n > b.n) {
      *this = a;
      merge(b);
    } else {
      *this = b;
      merge(a);
    }
  }
};
void row_reduce(vector<int64_t> &basis) {
  int B = basis.size();
  for (int i = 0; i < B; i++)
    for (int j = i + 1; j < B; j++)
      basis[i] = min(basis[i], basis[i] ^ basis[j]);
}
vector<int64_t> generate_all(vector<int64_t> basis, int M) {
  row_reduce(basis);
  int B = basis.size();
  vector<int64_t> change(B + 1, 0);
  int64_t prefix = 0;
  for (int i = 0; i < B; i++) {
    prefix ^= basis[i];
    change[i] = prefix;
  }
  change[B] = prefix;
  vector<int64_t> counts(M + 1, 0);
  int64_t value = 0;
  for (int mask = 0; mask < 1 << B; mask++) {
    counts[__builtin_popcountll(value)]++;
    value ^= change[__builtin_ctz(mask + 1)];
  }
  return counts;
}
vector<int64_t> build_orthogonal(vector<int64_t> basis, int M) {
  row_reduce(basis);
  int B = basis.size();
  vector<int> highest_bit(B, -1);
  vector<bool> bit_covered(M, false);
  for (int i = 0; i < B; i++) {
    highest_bit[i] = 63 - __builtin_clzll(basis[i]);
    bit_covered[highest_bit[i]] = true;
  }
  vector<int64_t> orthogonal;
  for (int bit = M - 1; bit >= 0; bit--)
    if (!bit_covered[bit]) {
      int64_t value = 1LL << bit;
      for (int i = 0; i < B; i++)
        value |= (basis[i] >> bit & 1) << highest_bit[i];
      orthogonal.push_back(value);
    }
  return orthogonal;
}
vector<int64_t> generate_from_orthogonal(vector<int64_t> basis, int M) {
  row_reduce(basis);
  int B = basis.size();
  vector<int64_t> orthogonal = build_orthogonal(basis, M);
  vector<int64_t> orthogonal_counts = generate_all(orthogonal, M);
  vector<int64_t> counts(M + 1, 0);
  vector<vector<int64_t>> choose(M + 1);
  for (int n = 0; n <= M; n++) {
    choose[n].resize(n + 1);
    choose[n][0] = choose[n][n] = 1;
    for (int r = 1; r < n; r++)
      choose[n][r] = choose[n - 1][r - 1] + choose[n - 1][r];
  }
  auto &&get_choose = [&](int n, int r) -> int64_t {
    if (r < 0 || r > n) return 0;
    return choose[n][r];
  };
  for (int c = 0; c <= M; c++) {
    vector<int64_t> w(M + 1, 0);
    for (int d = 0; d <= M; d++)
      for (int j = 0; j <= d; j++)
        w[d] +=
            (j % 2 == 0 ? 1 : -1) * get_choose(d, j) * get_choose(M - d, c - j);
    for (int d = 0; d <= M; d++) counts[c] += orthogonal_counts[d] * w[d];
    assert((counts[c] & ((1LL << (M - B)) - 1)) == 0);
    counts[c] >>= M - B;
  }
  return counts;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, M;
  cin >> N >> M;
  xor_basis<int64_t> basis_obj;
  for (int i = 0; i < N; i++) {
    int64_t a;
    cin >> a;
    basis_obj.add(a);
  }
  int B = basis_obj.n;
  vector<int64_t> basis(B);
  for (int i = 0; i < B; i++) basis[i] = basis_obj.basis[i];
  vector<int64_t> answers;
  if (B <= M / 2)
    answers = generate_all(basis, M);
  else
    answers = generate_from_orthogonal(basis, M);
  for (int i = 0; i <= M; i++) {
    mod_int answer = answers[i];
    answer *= mod_int(2).pow(N - B);
    cout << answer << (i < M ? ' ' : '\n');
  }
}