Solution

DP is very thoughtful.
Let i set power series fi of chocolate, where fi,0=1,fi,ai=2.
The answer is to convolute these symmetric differences.
The violence is to multiply each FWT.
Walsh transformation of set power series f

So f^i,S is 3 when ゝ S ∩ ai ゝ is even, otherwise − 1.
Consider a new set power series g, which is the sum of fi.
So g^S is some f *, S contributes − 1, some contributes 3.
It can be solved that there are 4 x = G ^ S + n for 3. Then the product of all f ^ *, S is 3 x (− 1)n − X.
The answer is to go back to FWT.
Because no empty set is allowed, it needs to be − 1s....

#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> Pairs;

const int MOD = 998244353;
const int INV2 = (MOD + 1) / 2;
const int N = 1 << 21;

inline char get(void) {
    static char buf[100000], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, 1, 100000, stdin);
        if (S == T) return EOF;
    }
    return *S++;
}
template<typename T>
inline void read(T &x) {
    static char c; x = 0; int sgn = 0;
    for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
    for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
    if (sgn) x = -x;
}

int n, m, mx, x;
int f[N];

inline void fwt(int* a, int f, int n) {
    static int x, y;
    for (int i = 1; i < n; i <<= 1)
        for (int j = 0; j < n; j += (i << 1))
            for (int k = 0; k < i; k++) {
                x = a[j + k]; y = a[j + k + i];
                a[j + k] = x + y;
                a[j + k + i] = x - y;
                if (f == -1) {
                    a[j + k] = (ll)a[j + k] * INV2 % MOD;
                    a[j + k + i] = (ll)a[j + k + i] * INV2 % MOD;
                }
            }
}
inline int pow(int a, int b) {
    int c = 1;
    while (b) {
        if (b & 1) c = (ll)c * a % MOD;
        b >>= 1; a = (ll)a * a % MOD;
    }
    return c;
}

int main(void) {
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    read(n);
    for (int i = 1; i <= n; i++) {
        read(x); mx = max(mx, x);
        f[x] += 2; f[0] += 1;
    }
    for (m = 1; m <= mx; m <<= 1);
    fwt(f, 1, m);
    for (int i = 0; i < m; i++) {
        int x = (f[i] + n) / 4;
        f[i] = (ll)pow(3, x) * pow(MOD - 1, n - x) % MOD;
    }
    fwt(f, -1, m);
    cout << (f[0] - 1 + MOD) % MOD << endl;
    return 0;
}