FWT_and

#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 100005, mod = 998244353;
ll A[maxn], b[maxn];//注意从下标为0开始存值
void FWT_and(ll *a, int n, int opt = 1){
    for(int i = 1; i < n; i <<= 1){
        for(int p = i << 1, j = 0; j < n; j += p){
            for(int k = 0; k < i; k++){
                if(opt == 1)    a[j+k] = (a[j+k] + a[i+j+k]) % mod;
                else    a[j+k] = (a[j+k] + mod - a[i+j+k]) % mod;
            }
        }   
    }
}
int main(){
    int n, tn = 1; scanf("%d", &n);
    //将最长的那个多项式的次数n进行变换得到tn 
    while(tn < 2 * n + 1) tn <<= 1;
    FWT_and(A, tn), FWT_and(B, tn);
    for(int i = 0; i < tn; i++) A[i] = A[i] * B[i] % mod;
    FWT_and(A, tn, -1);
    return 0;
}