#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 60;
ll f[MAX_N];
map<pair<int, ll>, ll> dp;
ll solve(int i, ll j) {
if (j < 0) return 0;
if (i == 0) return (j == 0 ? 1 : (f[i] == 0 ? 1 : 2));
if (dp.find({ i, j }) == dp.end()) dp[{i, j}] = -1;
ll& ret = dp[{i,j}];
if (ret != -1) return ret;
ret = solve(i-1, min({ j, (1ll << i)-1, f[i] }))
+ solve(i-1, min({ j-(1ll << i), (1ll << i)-1, f[i]-(1ll << i) }));
return ret;
}
ll count_tastiness(ll x, vector<ll> a) {
for (int i=0; i<MAX_N; ++i) {
ll sum = 0;
for (int j=0; j<min(i+1, (int)a.size()); ++j) sum += a[j] * (1ll << j);
f[i] = sum / x;
}
dp.clear();
ll ret = solve(MAX_N-1, (1ll << MAX_N)-1);
return ret;
}
