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;
namespace mine {
long long qread() {
  long long ans = 0, f = 1;
  char c = getchar();
  while (c < '0' or c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar();
  return ans * f;
}
void write(long long num) {
  if (num < 0) putchar('-'), num = -num;
  if (num >= 10) write(num / 10);
  putchar('0' + num % 10);
}
void write1(long long num) {
  write(num);
  putchar(' ');
}
void write2(long long num) {
  write(num);
  putchar('\n');
}
template <typename T>
inline bool chmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool chmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
bool IN(long long x, long long l, long long r) { return l <= x and x <= r; }
void GG() {
  puts("-1");
  exit(0);
}
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int mm(const int x) { return x >= MOD ? x - MOD : x; }
template <typename T>
void add(T &x, const int &y) {
  x = (x + y >= MOD ? x + y - MOD : x + y);
}
long long qpower(long long x, long long e, int mod = MOD) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = ans * x % mod;
    x = x * x % mod;
    e >>= 1;
  }
  return ans;
}
long long invm(long long x) { return qpower(x, MOD - 2); }
const int MM = 5e6 + 10;
long long fac[MM], facinv[MM], Inv[MM];
long long Comb(int n, int m) {
  return n < 0 or m < 0 or n < m
             ? 0
             : fac[n] * facinv[m] % MOD * facinv[n - m] % MOD;
}
void PRE() {
  fac[0] = 1;
  for (int i = (1), I = (MM - 1); i <= I; i++) fac[i] = fac[i - 1] * i % MOD;
  facinv[MM - 1] = invm(fac[MM - 1]);
  for (int i = (MM - 1), I = (1); i >= I; i--)
    facinv[i - 1] = facinv[i] * i % MOD;
  Inv[1] = 1;
  for (int i = (2), I = (MM - 1); i <= I; i++)
    Inv[i] = (MOD - MOD / i) * Inv[MOD % i] % MOD;
}
const int N = 1e6 + 10;
namespace BS {
long long bs[100];
int cnt, zero;
void clear() {
  memset(bs, 0, sizeof bs);
  cnt = zero = 0;
}
void insert(long long num) {
  for (int i = (60), I = (0); i >= I; i--)
    if (num & (1ll << (i))) {
      if (!bs[i]) {
        for (int t = (0), I = (i - 1); t <= I; t++)
          if (num & (1ll << (t))) num ^= bs[t];
        for (int t = (i + 1), I = (60); t <= I; t++)
          if (bs[t] & (1ll << (i))) bs[t] ^= num;
        bs[i] = num, cnt++;
        return;
      } else
        num ^= bs[i];
    }
  zero++;
}
long long findkth(long long k) {
  long long ret = 0, right = cnt;
  k -= (zero > 0);
  for (int i = (60), I = (0); i >= I; i--)
    if (bs[i]) {
      right--;
      if (k & (1ll << (right))) ret ^= bs[i], k -= (1ll << (right));
    }
  return k ? -1 : ret;
}
long long findrk(long long num) {
  long long rk = 0, right = cnt;
  for (int i = (60), I = (0); i >= I; i--)
    if (bs[i]) {
      right--;
      if (num & (1ll << (i))) rk |= (1ll << (right));
    }
  return rk;
}
};  // namespace BS
vector<long long> can;
int tim[100];
void dfs(int i, long long now) {
  if (i == ((int)(can).size()))
    tim[__builtin_popcountll(now)]++;
  else
    dfs(i + 1, now), dfs(i + 1, now ^ can[i]);
}
void main() {
  int n = qread(), m = qread();
  for (int i = (1), I = (n); i <= I; i++) BS::insert(qread());
  int B = BS::cnt;
  if (B <= 27) {
    for (int i = (0), I = (60); i <= I; i++)
      if (BS::bs[i]) can.push_back(BS::bs[i]);
    dfs(0, 0);
    for (int L = (0), I = (m); L <= I; L++)
      write1(tim[L] * qpower(2, n - B) % MOD);
  } else {
    PRE();
    long long pre[100][100];
    memset(pre, 0, sizeof pre);
    for (int L = (0), I = (m); L <= I; L++)
      for (int a = (0), I = (m); a <= I; a++)
        for (int k = (0), I = (a); k <= I; k++)
          add(pre[L][a], (k & 1 ? MOD - 1 : 1) * Comb(a, k) % MOD *
                             Comb(m - a, L - k) % MOD);
    for (int i = (0), I = (m - 1); i <= I; i++)
      if (!BS::bs[i]) {
        long long A = (1ll << (i));
        for (int j = (0), I = (m - 1); j <= I; j++)
          A |= (BS::bs[j] >> i) % 2 * (1ll << (j));
        can.push_back(A);
      }
    dfs(0, 0);
    for (int L = (0), I = (m); L <= I; L++) {
      long long sum = 0;
      for (int a = (0), I = (m); a <= I; a++)
        add(sum, tim[a] * pre[L][a] % MOD);
      write1(sum * qpower(2, n + MOD - 1 - m) % MOD);
    }
  }
}
};  // namespace mine
signed main() {
  srand(time(0));
  mine::main();
  printf("");
}