#include <iostream>
#include <vector>
using namespace std;
#define ll long long
ll solveSimple(vector<ll> a){
vector<ll> dp = {1, 0, 0, 0};
for(ll i = 0; i<a.size()-1; i++){
ll c = (a[i]-1)/2;
a[i+1] += c;
a[i] -= c * 2;
vector<ll> pdp = dp;
dp = {0, 0, 0, 0};
dp[0] = pdp[0] + pdp[1];
if(a[i] == 0) dp[1] = pdp[2] + pdp[3];
if(a[i] == 1){
dp[1] = pdp[0] + pdp[1];
dp[2] = pdp[2] + pdp[3];
}
if(a[i] == 2){
dp[1] = dp[2] = dp[0] = pdp[0] + pdp[1];
dp[3] = pdp[2] + pdp[3];
}
}
return dp[0] + dp[1];
}
ll solveBruteforce(ll x, vector<ll> a){
if(x>100000) return 1;
ll ans = 0;
for(ll i = 0; i<100000; i++){
vector<ll> t(64, 0);
for(int j = 0; j<a.size(); j++) t[j] = a[j];
ll isAns = 1;
for(ll j = 0; j<t.size()-1; j++){
if(((ll)((ll)1<<(ll)j)) & i){
if(t[j] < x){
isAns = 0;
break;
}
t[j] -= x;
}
t[j+1] += t[j]/2;
}
ans += isAns;
}
return ans;
}
ll count_tastiness(ll x, vector<ll> A){
vector<ll> a(200, 0);
for(ll i = 0; i<A.size(); i++) a[i] = A[i];
ll prev0 = -1;
ll prev2 = -1;
ll ans = 1;
vector<ll> dp = {1, 0, 0, 0};
for(ll i = 0; i<a.size()-1; i++){
ll k = a[i]%x;
a[i+1] += k/2;
a[i] -= k;
a[i]/=x;
}
return solveBruteforce(x, a);
}
