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;
const int RLEN = 1 << 20 | 1;
inline char gc() {
  static char ibuf[RLEN], *ib, *ob;
  (ib == ob) && (ob = (ib = ibuf) + fread(ibuf, 1, RLEN, stdin));
  return (ib == ob) ? EOF : *ib++;
}
inline int read() {
  char ch = gc();
  int res = 0;
  bool f = 1;
  while (!isdigit(ch)) f ^= ch == '-', ch = gc();
  while (isdigit(ch)) res = (res + (res << 2) << 1) + (ch ^ 48), ch = gc();
  return f ? res : -res;
}
inline long long readll() {
  char ch = gc();
  long long res = 0;
  bool f = 1;
  while (!isdigit(ch)) f ^= ch == '-', ch = gc();
  while (isdigit(ch)) res = (res + (res << 2) << 1) + (ch ^ 48), ch = gc();
  return f ? res : -res;
}
inline int readstring(char *s) {
  int top = 0;
  char ch = gc();
  while (isspace(ch)) ch = gc();
  while (!isspace(ch) && ch != EOF) s[++top] = ch, ch = gc();
  s[top + 1] = '\0';
  return top;
}
template <typename tp>
inline void chemx(tp &a, tp b) {
  a = max(a, b);
}
template <typename tp>
inline void chemn(tp &a, tp b) {
  a = min(a, b);
}
const int mod = 998244353;
inline int add(int a, int b) {
  return (a + b) >= mod ? (a + b - mod) : (a + b);
}
inline int dec(int a, int b) { return (a < b) ? (a - b + mod) : (a - b); }
inline int mul(int a, int b) {
  static long long r;
  r = (long long)a * b;
  return (r >= mod) ? (r % mod) : r;
}
inline void Add(int &a, int b) { a = (a + b) >= mod ? (a + b - mod) : (a + b); }
inline void Dec(int &a, int b) { a = (a < b) ? (a - b + mod) : (a - b); }
inline void Mul(int &a, int b) {
  static long long r;
  r = (long long)a * b;
  a = (r >= mod) ? (r % mod) : r;
}
inline int ksm(int a, int b, int res = 1) {
  for (; b; b >>= 1, Mul(a, a)) (b & 1) && (Mul(res, a), 1);
  return res;
}
inline int Inv(int x) { return ksm(x, mod - 2); }
inline int fix(long long x) {
  x %= mod;
  return (x < 0) ? x + mod : x;
}
const int N = 200005, M = 66;
long long bas[M], a[M], b[M];
int n, m, k, sz, p[M], C[M][M];
inline void init_C() {
  for (int i = 0; i < M; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++) C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
  }
}
void dfs(int pos, long long res) {
  if (pos >= k) {
    p[__builtin_popcountll(res)]++;
    return;
  }
  dfs(pos + 1, res ^ a[pos]), dfs(pos + 1, res);
}
void dfs2(int pos, long long res) {
  if (pos >= m - k) {
    {
      p[__builtin_popcountll(res)]++;
      return;
    }
  }
  dfs2(pos + 1, res ^ b[pos]), dfs2(pos + 1, res);
}
inline void solve2() {
  for (int i = 0; i < m - k; i++) {
    long long res = 0;
    for (int j = 0; j < k; j++)
      if (a[j] & (1ll << i)) res ^= 1ll << j;
    b[i] = res | (1ll << (m - 1 - i));
  }
  dfs2(0, 0);
  for (int i = 0; i <= m; i++) {
    int res = 0;
    for (int j = 0; j <= m; j++) {
      int c = 0;
      for (int k = 0; k <= i; k++) {
        int now = mul(C[m - j][i - k], C[j][k]);
        if (k & 1)
          Dec(c, now);
        else
          Add(c, now);
      }
      Add(res, mul(c, p[j]));
    }
    cout << mul(res, mul(ksm(2, n - k), Inv(ksm(2, m - k)))) << " ";
  }
}
inline void solve1() {
  dfs(0, 0);
  for (int i = 0; i <= m; i++) cout << mul(p[i], ksm(2, n - k)) << " ";
  exit(0);
}
inline void insert(long long x) {
  for (int i = m - 1; ~i; i--)
    if ((x >> i) & 1) {
      if (!bas[i]) {
        sz++, bas[i] = x;
        return;
      }
      x ^= bas[i];
    }
}
int main() {
  init_C();
  n = read(), m = read();
  for (int i = 1; i <= n; i++) insert(readll());
  for (int i = 0; i < m; i++)
    if (bas[i]) {
      for (int j = 0; j < i; j++)
        if (bas[j] && ((bas[i] >> j) & 1)) bas[i] ^= bas[j];
      long long x = 0;
      for (int j = 0; j < m; j++)
        if (!bas[j]) {
          x <<= 1, x += (bas[i] >> j) & 1;
        }
      a[k] = x + (1ll << (m - 1 - k)), k++;
    }
  if (k <= 26)
    solve1();
  else
    solve2();
}