#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
long long x;
vector<long long> a;
vector<long long> cnt;
map<pair<int, long long>, long long> dp;
long long bt(int b, long long c) {
if (b < 0) {
return 1;
}
//if (c > 2 * x) {
//c = 2 * x;
//}
if (dp.count({b, c})) {
return dp[{b, c}];
}
long long& ret = dp[{b, c}];
long long org = (b < (int) a.size() ? a[b] : 0);
ret = bt(b - 1, (c - org) * 2 + (b > 0 ? cnt[b - 1] : 0));
if (c >= x) {
ret += bt(b - 1, (c - max(x, org)) * 2 + (b > 0 ? cnt[b - 1] : 0));
}
return ret;
}
long long count_tastiness(long long x_, vector<long long> a_) {
x = x_;
cnt = a = a_;
for (int i = 0; ; ++i) {
long long cur = cnt[i];
//cout << "I: " << i << endl;
if (cur > 1) {
cnt[i] = cur % 2;
if (i == (int) cnt.size() - 1) {
cnt.push_back(cur / 2);
} else {
cnt[i + 1] += cur / 2;
}
} else if (i == (int) cnt.size() - 1) {
break;
}
}
//cout << "CNT: ";
//for (int i : cnt) {
//cout << i << ' ';
//}
//cout << '\n';
int lg = (int) cnt.size();
long long ans = bt(lg - 1, cnt[lg - 1]);
dp.clear();
return ans;
}
