#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
using ui = __int128_t; using ui4 = array<ui,4>;
#include "biscuits.h"
vector<ui4> mem;
//left, right, height, # contained
ll root;
ll split(ll v, ll y) {
//handle height = -1
ll ht = mem[v][2];
if (ht==-1) {
mem.push_back({-1,-1,-1,1});
return (mem.size()-1);
}
if (y>=(((ui)1)<<ht)) {
if (mem[v][1]!=-1) {
ll vnew = split(mem[v][1],y-(((ui)1)<<ht));
mem.push_back({mem[v][0],vnew,ht,mem[mem[v][0]][3]+mem[vnew][3]});
} else {
mem.push_back({mem[v][0],-1,ht,mem[mem[v][0]][3]});
}
return (mem.size()-1);
} else {
ll vnew = split(mem[v][0],y);
mem.push_back({vnew,-1,ht,mem[vnew][3]});
return (mem.size()-1);
}
}
ll count_tastiness(ll x, vector<ll> a0) {
ll k = a0.size();
mem.clear();
mem.push_back({-1,-1,-1,1});
root = 0;
while (a0.size()<=60) {
a0.push_back(0);
}
k = a0.size();
ui y0 = 0; //current sum
for (ll i=0;i<k;i++) {
y0 += ((ui)a0[i])<<i;
ui z0 = y0/x;
z0 = min(z0,(((ui)1)<<(i+1))-1);
if (z0>=(((ui)1)<<i)) {
ll vnew = split(root,z0-(((ui)1)<<(i)));
mem.push_back({root,vnew,i,mem[root][3]+mem[vnew][3]});
root = mem.size()-1;
}
}
return mem[root][3];
}
