#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define cout cerr
#define trace(x) for (auto &el : x) cout << el << " "
using vi = vector<int>;
using vvi = vector<vi>;
int k = 127;
int brute(int x, vi a) {
int ans = 0;
int mx = 0; for (int i = 0; i < k; i++) mx += a[i]*(1LL<<i);
for (int i = 0; i <= mx; i++) {
vi avail = a; bool good = true;
for (int bit = 0; bit < k; bit++) {
if ((1LL<<bit) > i) break;
bool use = i & 1LL<<bit;
if (use && avail[bit] < x) good = false;
int rem = use ? avail[bit] - x : avail[bit];
avail[bit+1] += rem / 2;
}
if (good) {
ans++;
// cout << i << " ";
}
}
// cout << "\n";
return ans;
}
// start by pushing everything upstream, with limit x
// now the difference between using bit i or pushing it up to i+1
int count_tastiness(int x, vi a) {
while (a.size() <= k) a.push_back(0);
for (int i = 0; i < k; i++) {
if (a[i] <= x+1) continue;
a[i+1] += (a[i]-x) / 2;
a[i] -= 2 * ((a[i]-x) / 2);
}
// trace(a); cout << "\n";
vvi dp(k+1, vi(2, 0)); dp[k][0] = dp[k][1] = 1;
vi d1(k+1), d2(k+1); for (int i = 0; i < k; i++) d1[i] = a[i] == 0 ? x : ((x - a[i]) % x) % x;
// dp[i][0] = how many possibilities after processing the suffix i..k and providing no extra carry
// dp[i][1] = how many more possibilities after processing the suffix i..k and providing an extra carry
// cout << "yo\n";
// trace(d1); cout << "\n";
// trace(a); cout << "\n";
for (int i = k-1; i >= 0; i--) {
if (a[i] >= x) {
dp[i][0] = 2*dp[i+1][0];
int R = d1[i+1];
int A = a[i] / 2;
if (A > 0 && A >= d1[i+1]) {
dp[i][0] += dp[i+1][1];
dp[i][1] = dp[i+1][1];
} else {
// int nd = 2*d1[i+1] - a[i];
// cout << "i " << i << " od " << d1[i] << " nd " << nd << "\n";
// d1[i] = nd;
dp[i][1] = dp[i+1][1];
}
} else {
dp[i][0] = dp[i+1][0]; // no change
dp[i][1] = dp[i+1][0];
}
}
// int ex = brute(x, a);
// cout << "BRUTE: " << ex << " DP: " << dp[0][0] << "\n";
return dp[0][0];
}
