#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 = 60;
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);
}
vvi dp(k+1, vi(x+1));
dp[60][0] = 1; // 0 in each
for (int bit = 59; bit >= 0; bit--) {
for (int carry = 0; carry <= x; carry++) {
dp[bit][carry] += dp[bit+1][(a[bit] + carry) / 2];
if (a[bit] + carry >= x) dp[bit][carry] += dp[bit+1][(a[bit] + carry - x) / 2];
}
}
// map<pair<int, int>, int> memo;
// auto dfs = [&](auto &&self, int carry, int bit)->int {
// if (bit >= 60 && carry == 0) return 1; // 0 in each
// if (memo.count({carry, bit})) return memo[{carry, bit}];
// int ans = self(self, (a[bit] + carry) / 2, bit + 1); // don't set bit
// if (a[bit] + carry >= x) ans += self(self, (a[bit] + carry -x) / 2, bit+1); // set bit if possible;
// return memo[{carry, bit}] = ans;
// return ans;
// };
// int ex = brute(x, a);
// cout << "BRUTE: " << ex << " DP: " << dp[0][0] << "\n";
return dp[0][0];
// return 0;
}
