#include <bits/stdc++.h>
#define int long long
using namespace std;
#include "biscuits.h"
// dp[cur][nbNecessaire] = nb de facons de choisir y si il faut nbNecessaire et
// qu'on autorise que ceux avec des bits <= cur
//
// dp[cur][nbNecessaire] = dp[cur-1][2 * (max(0, nbNecessaire - a[cur]))]
// + dp[cur-1][2 * (max(0, x + nbNecessaire - a[cur]))]
// dp[-1][0] = 1
//
//
// dp2[cur][nbSupplements] = dp2[cur+1][ (nbSupplements + a[cur]) / 2]
// + dp2[cur+1][(nbSupplements + a[cur] - x) / 2]
//
// dp2[256][nbSupplements] = 1
//
//
// Si a[i] > x on peut ajouter (a[i] - x) / 2 à a[i+1]
// Donc a[i] <= x pour tout i
const int MAX = 256;
int dfs(const vector<int> &a, int nbRestants, int x, int curBit) {
if (curBit == MAX)
return 1;
if (curBit < (int)a.size())
nbRestants += a[curBit];
int sol = dfs(a, nbRestants / 2, x, curBit + 1);
if (nbRestants >= x)
sol += dfs(a, (nbRestants - x) / 2, x, curBit + 1);
return sol;
}
int count_tastiness(int x, vector<int> a) {
return dfs(a, 0, x, 0);
if (x > (int)1e5)
return 1;
array<vector<int>, 2> arr;
arr.fill(vector<int>(x + 2, 0));
for (int i(0); i < (int)a.size(); ++i) {
if (a[i] > x) {
if (i + 1 == (int)a.size())
a.push_back(0);
a[i + 1] += (a[i] - x) / 2;
a[i] -= 2 * ((a[i] - x) / 2);
}
}
for (int nbRestants = 0; nbRestants <= x + 1; ++nbRestants)
arr[(MAX - 1) % 2][nbRestants] = 1;
for (int i(MAX - 2); i >= 0; --i) {
int cur = i % 2;
int prev = !cur;
for (int nbRestants = 0; nbRestants <= x + 1; ++nbRestants) {
arr[cur][nbRestants] = 0;
int tot = nbRestants;
if (i < (int)a.size())
tot += a[i];
if (tot >= x)
arr[cur][nbRestants] += arr[prev][(tot - x) / 2];
arr[cur][nbRestants] += arr[prev][tot / 2];
}
}
return arr[0][0];
}
