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>
using namespace std;
long long inf;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T, class T2>
long long chkmin(T &a, T2 b) {
  return a > b ? a = b, 1 : 0;
}
template <class T, class T2>
long long chkmax(T &a, T2 b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T, class T2>
T mmin(T a, T2 b) {
  return a < b ? a : b;
}
template <class T, class T2>
T mmax(T a, T2 b) {
  return a > b ? a : b;
}
template <class T>
T aabs(T a) {
  return a < 0 ? -a : a;
}
template <class T>
long long dcmp(T a, T b) {
  return a > b;
}
template <long long *a>
long long cmp_a(long long first, long long second) {
  return a[first] < a[second];
}
struct __INIT__ {
  __INIT__() { memset(&inf, 0x3f, sizeof(inf)); }
} __INIT___;
namespace io {
const long long SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
long long f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char first) {
  *oS++ = first;
  if (oS == oT) flush();
}
template <typename A>
inline bool read(A &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(char &first) {
  while ((first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                               (iS == iT ? EOF : *iS++))
                            : *iS++)) == ' ' ||
         first == '\n' || first == '\r')
    ;
  return first != EOF;
}
inline bool read(char *first) {
  while ((*first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                                (iS == iT ? EOF : *iS++))
                             : *iS++)) == '\n' ||
         *first == ' ' || *first == '\r')
    ;
  if (*first == EOF) return 0;
  while (!(*first == '\n' || *first == ' ' || *first == '\r' || *first == EOF))
    *(++first) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                           : *iS++);
  *first = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &first, B &...second) {
  return read(first) && read(second...);
}
template <typename A>
inline bool write(A first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char first) {
  putc(first);
  return 0;
}
inline bool write(const char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
inline bool write(char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A first, B... second) {
  return write(first) || write(second...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
long long a[55], b[55], l[55];
const long long p = 998244353;
long long n, m, first, k, pw = 0;
void insert(long long first) {
  for (long long i = m - 1; ~i; --i)
    if (first & (1ll << i)) {
      if (!l[i]) {
        l[i] = first;
        for (long long j = 0; j < i; ++j)
          if (l[i] & (1ll << j)) l[i] ^= l[j];
        for (long long j = i + 1; j < m; ++j)
          if (l[j] & (1ll << i)) l[j] ^= l[i];
        return;
      } else {
        first ^= l[i];
      }
    }
  ++pw;
}
long long f1[1 << 20 | 5], f2[1 << 20 | 5];
long long cnt[55];
void dp(long long *a, long long k, long long *cnt) {
  long long m = mmin(k, 14), m2 = k - m;
  for (long long i = 0; i < m; ++i) f1[1 << i] = a[i + 1];
  for (long long i = 0; i < m2; ++i) f2[1 << i] = a[i + m + 1];
  for (long long i = 1; i < 1 << m; ++i)
    if (i & (i - 1)) f1[i] = f1[i & (i - 1)] ^ f1[i & (-i)];
  for (long long i = 1; i < 1 << m2; ++i)
    if (i & (i - 1)) f2[i] = f2[i & (i - 1)] ^ f2[i & (-i)];
  for (long long i = 0; i < 1 << m; ++i)
    for (long long j = 0; j < 1 << m2; ++j)
      ++cnt[__builtin_popcount(i) + __builtin_popcount(j) +
            __builtin_popcountll(f1[i] ^ f2[j])];
}
long long xc[55];
long long w[55][55];
long long c[55];
long long C[55][55];
void make(long long *a, long long *b, long long k) {
  for (long long i = 0; i < k; ++i) a[i] = a[i + 1] << k | 1ll << i;
  for (long long i = 0; i < m; ++i) c[i] = 1ll << i;
  for (long long i = 0; i < k; ++i) {
    for (long long j = i + 1; j < m; ++j)
      if (__builtin_parityll(a[i] & c[j])) c[j] ^= c[i];
  }
  for (long long i = 1; i <= (m - k); ++i)
    b[i] = c[i + k - 1] & ((1LL << k) - 1);
}
signed main() {
  read(n, m);
  for (long long i = 1; i <= n; ++i) {
    read(first);
    insert(first);
  }
  for (long long i = 0; i < m; ++i)
    if (l[i]) {
      ++k;
      long long L = 0;
      for (long long j = 0; j < i; ++j)
        if (!l[j]) {
          if (l[i] & (1ll << j)) a[k] |= 1LL << L;
          ++L;
        }
    }
  if (k <= 27) {
    dp(a, k, cnt);
    long long s = 1;
    for (; pw; --pw) s = (s << 1) % p;
    for (long long i = 0; i <= m; ++i)
      write(cnt[i] * s % p, i == m ? '\n' : ' ');
  } else {
    make(a, b, k);
    dp(b, m - k, xc);
    pw += k;
    pw -= m;
    for (long long i = 0; i <= m; ++i) {
      C[i][0] = C[i][i] = 1;
      for (long long j = 1; j < i; ++j)
        C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
    }
    for (long long i = 0; i <= m; ++i) {
      for (long long j = 0; j <= m; ++j) {
        for (long long k = 0; k <= i && k <= j; k += 2) {
          w[i][j] = (w[i][j] + C[i][k] * C[m - i][j - k]) % p;
        }
        for (long long k = 1; k <= i && k <= j; k += 2) {
          w[i][j] = (w[i][j] - C[i][k] * C[m - i][j - k]) % p;
        }
        if (w[i][j] < 0) w[i][j] += p;
      }
    }
    long long s = 1;
    if (pw < 0)
      for (; pw < 0; ++pw) s = (s * (p + 1) >> 1) % p;
    else
      for (; pw; --pw) s = (s << 1) % p;
    for (long long i = 0; i <= m; ++i)
      for (long long j = 0; j <= m; ++j)
        cnt[j] = (cnt[j] + xc[i] * w[i][j]) % p;
    for (long long i = 0; i <= m; ++i)
      write(cnt[i] * s % p, i == m ? '\n' : ' ');
  }
  return 0;
}