#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);
for (int i = 0; i < n; i++) {
cat cur = cat(1) << i;
for (int j = i-1; j >= 0; j--) {
cur ^= cat(1) << j;
ll carry = 0;
bool bad = 0;
for (int k = 0; k <= i && !bad; k++) {
carry /= 2;
carry += a[k];
if ((cur >> k) & 1) carry -= x;
if (carry < 0) bad = 1;
}
if (bad) {
cur ^= cat(1) << j;
}
}
bool bad = 0;
ll carry = 0;
for (int k = 0; k <= i && !bad; k++) {
carry /= 2;
carry += a[k];
if ((cur >> k) & 1) carry -= x;
if (carry < 0) bad = 1;
}
if (bad) {
assert(cur == cat(1) << i);
bound[i] = -1;
} else {
bound[i] = cur ^ (cat(1) << i);
}
}
return rec(n - 1, (cat(1) << n) - 1);
}
