---

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;//三年竞赛一场空，不开long long见祖宗

//typedef __int128 lll;

#define print(i) cout << "debug: " << i << endl

#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define mem(a, b) memset(a, b, sizeof(a))

#define pb(a) push_back(a)

#define x first

#define y second

typedef pair<int, int> pii;

const double eps = 1e-8;

const ll mod = 1000000000;

const int maxn = 1e6 + 10;

const int inf = 0x3f3f3f3f;

 

ll dp[maxn];

 

void init()

{

    dp[0] = 1;

    for(int i = 1; i&n...