#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
typedef long long ll;
const int SHIFT = 61;
using cat = __int128;
map<pair<int, cat>, ll> dp;
vector<cat> bound;
ll rec(int c, cat b) {
if (c < 0) return 1;
if (dp.count({c, b})) return dp[{c, b}];
ll ans = 0;
// set as a 0
if ((b >> c) & 1) {
ans += rec(c - 1, (cat(1) << c) - 1);
} else {
ans += rec(c - 1, b);
}
// set as a 1
if (((b >> c) & 1) && bound[c] != -1) {
ans += rec(c - 1, min(b ^ (cat(1) << c), bound[c]));
}
return dp[{c, b}] = ans;
}
long long count_tastiness(long long x, std::vector<long long> a) {
int n = SHIFT + sz(a);
while (sz(a) < n) a.push_back(0);
dp.clear();
bound.resize(n);
vector<ll> pre(n);
ll base = 0;
for (int i = 0; i < n; i++) {
base /= 2;
pre[i] = base;
base += a[i];
}
for (int i = 0; i < n; i++) {
if (a[i] >= x) {
bound[i] = (cat(1) << i) - 1;
continue;
}
ll need = x - a[i];
if (need > pre[i]) {
bound[i] = -1;
continue;
}
cat cur = 0;
for (int j = i-1; j >= 0; j--) {
need *= 2;
if (pre[j] + a[j] - x >= need) {
need -= a[j] - x;
cur |= cat(1) << j;
} else {
need -= a[j];
}
need = max(need, 0LL);
}
bound[i] = cur;
}
return rec(n - 1, (cat(1) << n) - 1);
}
