#include "biscuits.h"
#include <cassert>
#include <algorithm>
#include <cstdio>
long long x_leq_10000(long long x, std::vector<long long> a) {
while(a.size() < 60) a.push_back(0);
for(int i = 0; i+1 < (int)a.size(); i++) {
if(a[i] <= x) continue;
if((a[i]&1)==(x&1)) {
a[i+1] += (a[i] - x) >> 1;
a[i] = x;
} else {
a[i+1] += (a[i] - x - 1) >> 1;
a[i] = x+1;
}
}
long long dp[10010]{}, new_dp[10010]{};
dp[0] = 1, dp[x] = 1;
for(int i = (int)(a.size()) - 1; i >= 0; i--) {
for(int qtd = 0; qtd <= x; qtd++)
new_dp[qtd] = dp[(a[i] + qtd)/2] + (a[i]+qtd >= x ? dp[(a[i] + qtd - x) / 2] : 0);
for(int qtd = 0; qtd <= x; qtd++)
dp[qtd] = new_dp[qtd];
}
return dp[0];
}
long long count_tastiness(long long x, std::vector<long long> a) {
if(x <= 10000) return x_leq_10000(x, a);
std::vector<long long> val(200000);
int pos = 1;
while(a.size() < 60) a.push_back(0);
for(int i = 1; i < (int)a.size(); i++)
a[i] = (1ll << i) * a[i] + a[i-1];
for(int i = 0; i < 60; i++) {
long long pot = (1ll << i);
int last = std::upper_bound(val.begin(), val.begin()+pos, a[i] / x - (1ll << i)) - val.begin();
for(int j = 0; j < last; j++)
val[pos++] = val[j]|pot;
}
return pos;
}
