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>
template <int MOD>
struct Integral {
  int v_ = 0;
  template <typename T>
  Integral(T v) : v_(norm(v)) {
    static_assert(std::is_integral<T>::value, "input should be an integral.");
  }
  Integral() = default;
  ~Integral() = default;
  template <typename T>
  T norm(T v) const {
    if constexpr (std::is_same<long long, T>::value) {
      v %= MOD;
      if (v < 0) v += MOD;
    } else {
      if (v >= MOD) v -= MOD;
      if (v < 0) v += MOD;
      if (v >= MOD || v < 0) {
        v %= MOD;
        if (v < 0) v += MOD;
      }
    }
    return v;
  }
  int val() const { return v_; }
  Integral& operator+=(const Integral& rhs) {
    v_ += rhs.val();
    if (v_ >= MOD) v_ -= MOD;
    return *this;
  }
  Integral& operator-=(const Integral& rhs) {
    v_ += MOD - rhs.val();
    if (v_ >= MOD) v_ -= MOD;
    return *this;
  }
  Integral& operator*=(const Integral& rhs) {
    v_ = v_ * 1LL * rhs.val() % MOD;
    return *this;
  }
  Integral& operator/=(const Integral& rhs) {
    v_ = v_ * 1LL * rhs.inv().val() % MOD;
    return *this;
  }
  Integral operator+(const Integral& rhs) const {
    Integral ret = *this;
    return ret += rhs;
  }
  Integral operator-(const Integral& rhs) const {
    Integral ret = *this;
    return ret -= rhs;
  }
  Integral operator*(const Integral& rhs) const {
    Integral ret = *this;
    return ret *= rhs;
  }
  Integral operator/(const Integral& rhs) const {
    Integral ret = *this;
    return ret /= rhs;
  }
  bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
  bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator-() const { return Integral(-val()); }
  const Integral& operator++() {
    v_ += 1;
    if (v_ >= MOD) v_ -= MOD;
    return *this;
  }
  const Integral operator++(int) {
    Integral ret = *this;
    ++(*this);
    return ret;
  }
  const Integral& operator--() {
    v_ += MOD - 1;
    if (v_ >= MOD) v_ -= MOD;
    return *this;
  }
  const Integral operator--(int) {
    Integral ret = *this;
    --(*this);
    return ret;
  }
  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for (; b; b >>= 1, a = a * a % MOD)
      if (b & 1) ret = ret * a % MOD;
    return ret;
  }
  Integral inv() const { return power(MOD - 2); }
};
template <int MOD>
std::string to_string(const Integral<MOD>& v) {
  return std::string("{") + std::to_string(v.val()) + "}";
}
template <int MOD, bool kAllowBruteForce = false>
struct Binomial {
  std::vector<Integral<MOD>> factor, inv_factor;
  explicit Binomial(int n = 0) : factor(n + 1), inv_factor(n + 1) {
    factor[0] = 1;
    for (int i = 1; i <= n; ++i) factor[i] = factor[i - 1] * i;
    inv_factor[n] = factor[n].inv();
    for (int i = n; i >= 1; --i) inv_factor[i - 1] = inv_factor[i] * i;
  }
  ~Binomial() = default;
  template <typename T>
  Integral<MOD> operator()(T a, T b) const {
    if (a < b || b < 0) return 0;
    if (a < factor.size()) return factor[a] * inv_factor[b] * inv_factor[a - b];
    if constexpr (!kAllowBruteForce) {
      throw std::out_of_range("Binomial");
    } else {
      b = std::min(b, a - b);
      Integral<MOD> ret = 1;
      for (T i = 1; i <= b; ++i) ret = ret * (a + 1 - i) / i;
      return ret;
    }
  }
};
template <int MOD>
struct PowerTable : public std::vector<Integral<MOD>> {
  PowerTable(int n, const Integral<MOD>& g) {
    static_assert(sizeof(PowerTable) == sizeof(std::vector<Integral<MOD>>), "");
    this->resize(n + 1);
    this->at(0) = 1;
    this->at(1) = g;
    for (int i = 2; i < this->size(); ++i)
      this->at(i) = this->at(i - 1) * this->at(1);
  }
};
const int MOD = 998244353;
using Mint = Integral<MOD>;
using Binom = Binomial<MOD>;
Binom binom(200000);
PowerTable<MOD> pw2(200000, 2);
PowerTable<MOD> pw_inv2(200000, Mint(2).inv());
using LL = long long;
const int kDim = 53 + 5;
Mint f[kDim];
Mint B[kDim];
std::vector<LL> a;
int n, m, k;
std::vector<int> major_dims, minor_dims;
std::vector<LL> influences;
void search_base(int at, LL mask) {
  if (at == a.size()) {
    ++f[__builtin_popcountll(mask)];
    return;
  }
  search_base(at + 1, mask);
  search_base(at + 1, mask ^ a[at]);
}
void search_minor_dim(int at, LL mask, LL influence_mask) {
  if (at == minor_dims.size()) {
    int r = __builtin_popcountll(mask) + __builtin_popcountll(influence_mask);
    ++B[r];
    return;
  }
  search_minor_dim(at + 1, mask, influence_mask);
  search_minor_dim(at + 1, mask | 1LL << minor_dims[at],
                   influence_mask ^ influences[at]);
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;
  reader >> n >> m;
  a.resize(n);
  for (int i = 0; i < n; ++i) {
    reader >> a[i];
  }
  k = 0;
  for (int dim = 0; dim < m; ++dim) {
    for (int i = k; i < n; ++i) {
      if (a[i] >> dim & 1) {
        std::swap(a[k], a[i]);
        break;
      }
    }
    if (k >= n || (~a[k] >> dim & 1)) {
      minor_dims.emplace_back(dim);
      continue;
    }
    for (int i = 0; i < n; ++i)
      if (i != k && (a[i] >> dim & 1)) a[i] ^= a[k];
    major_dims.emplace_back(dim);
    ++k;
  }
  a.resize(k);
  if (k <= m - k) {
    search_base(0, 0LL);
  } else {
    influences.resize(minor_dims.size());
    for (int i = 0; i < minor_dims.size(); ++i) {
      for (int j = 0; j < k; ++j)
        if (a[j] >> minor_dims[i] & 1) influences[i] |= 1LL << j;
    }
    search_minor_dim(0, 0LL, 0LL);
    for (int c = 0; c <= m; ++c) {
      for (int r = 0; r <= m; ++r) {
        Mint h = 0;
        for (int j = 0; j <= std::min(r, c); ++j) {
          Mint val = binom(r, j) * binom(m - r, c - j);
          if (j & 1)
            h -= val;
          else
            h += val;
        }
        f[c] += pw2[k] * pw_inv2[m] * h * B[r];
      }
    }
  }
  for (int c = 0; c <= m; ++c) {
    Mint result = f[c] * pw2[n - k];
    printf("%d%c", result.val(), " \n"[c == m]);
  }
}