Question: Give you a number of a, ask you to use n multiples of 3 or (or) operation can get a number of solutions, note: 0 is also

Idea: If the binary representation of a is regarded as a set and a subset with Part 1 of a set is regarded as a subset of a, then the problem can be converted into how many subsets of a can be obtained by operation. Then we define S[i][j] to represent the number of subsets of I 1 and J 2. (Current binary bit weight mod 3, which makes it easy to determine the multiples of 3) It is obvious that it can work well. The number of combinations is calculated. But the answer will be repeated, so we need to use exclusion to calculate the answer.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 64;
const int maxn = 1e3 + 10;
const ll mod = 998244353;
ll C[N][N], S[N][N]; //S[i][j] denotes the number of subsets of I 1 and j 2

ll powermod(ll a, ll b, ll c)
{
    a = a % c;
    ll res = 1;
    while(b)
    {
        if(b & 1)
            res = res * a % c;
        b >>= 1;
        a = a * a % c;
    }
    return res % c;
}
void init()
{
    C[0][0] = 1;
    for(int i = 1; i < N; ++i) //Combinatorial number
    {
        C[i][0] = 1;
        for(int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j] + mod) % mod;
    }
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            for(int p = 0; p <= i; ++p)
            {
                for(int q = 0; q <= j; ++q)
                {
                    if((p + 2 * q) % 3)
                        continue;
                    S[i][j] = (S[i][j] + C[i][p] * C[j][q] % mod + mod) % mod;
                }
            }
        }
    }
    S[0][0] = 1;
}

int main()
{
    init();
    int t;
    scanf("%d", &t);
    while(t--)
    {
        ll n, a, x = 0, y = 0;
        scanf("%lld%lld", &n, &a);
        for(int i = 0; i < N; ++i)
        {
            if(a & (1ll << i))
            {
                if(i & 1) //Odd digit
                    x++; //Statistical mod3==1 digits
                else
                    y++; //2
            }
        }
        ll ans = 0;
        for(int i = 0; i <= x; ++i)
        {
            for(int j = 0; j <= y; ++j)
            {   //The n-th power of S[i][j] can be expressed as the number of subset schemes of S[i][j] in bitwise or in the state of the result by multiples of n threes.
                ll tmp = C[x][i] * C[y][j] % mod * powermod(S[i][j], n, mod) % mod;
                if((x + y - i - j) & 1) //Tolerance exclusion
                    tmp = -tmp;
                ans = (ans + tmp + mod) % mod;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}