#ifdef LIS05ST
#define _GLIBCXX_DEBUG
#define _GLIBCXX_DEBUG_PEDANTIC
#endif
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2,popcnt,lzcnt,bmi,bmi2")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef __int128_t i128;
#define int long long
long long count_tastiness(long long x, std::vector<long long> a){
int k=a.size();
while(a.size()<63)a.push_back(0);
k=63;
for(int i=0;i<k-1;i++){
if(a[i]>=3){
if(a[i]&1)a[i+1]+=a[i]/2,a[i]=1;
else a[i+1]+=(a[i]-2)/2,a[i]=2;
}
}
ll dp[k+1][2][2]={};
dp[0][0][0]=1;
for(int i=1;i<=k;i++){
if(a[i-1]==0){
// не перекидаємо з попереднього
dp[i][0][0]+=dp[i-1][0][0]+dp[i-1][1][0];
// перекидаємо з попереднього
dp[i][1][0]+=dp[i-1][0][1]+dp[i-1][1][1];
}
if(a[i-1]==1){
// не перекидаємо з попереднього
dp[i][0][0]+=dp[i-1][0][0]+dp[i-1][1][0];
dp[i][1][0]+=dp[i-1][0][0]+dp[i-1][1][0];
// перекидаємо з попереднього
dp[i][0][1]+=dp[i-1][0][1]+dp[i-1][1][1];
}
if(a[i-1]==2){
// не перекидаємо з попереднього
dp[i][0][0]+=dp[i-1][0][0]+dp[i-1][1][0];
dp[i][1][0]+=dp[i-1][0][0]+dp[i-1][1][0];
dp[i][0][1]+=dp[i-1][0][0]+dp[i-1][1][0];
// перекидаємо з попереднього
dp[i][1][1]+=dp[i-1][0][1]+dp[i-1][1][1];
}
}
return dp[62][0][0]+dp[62][1][0];
}
/*
1 2 2 0
2 4
2 2 2 1 0
1 1 1 1 0
*/
#define MULTITESTS false
void solve(int testCase){
}
void precalc(){
}
/*
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
precalc();
int t=1;
if(MULTITESTS)cin>>t;
for(int i=1;i<=t;i++){
auto t1=clock();
solve(i);
auto t2=clock();
float delta=t2-t1;
delta/=CLOCKS_PER_SEC;
#ifdef LIS05ST
cout<<"("<<i<<")------------"<<fixed<<setprecision(2)<<delta<<"s\n";
#endif
}
}*/
