#include "biscuits.h"
#include <bits/stdc++.h>
#define ent '\n'

using namespace std;
typedef long long ll;

ll dp[71], mx[71];
ll a[71];
ll n, k;

ll get(int i, ll val, int pos) {
    if(val < 0) return 0;
    if(i < 0) return 1;
    ll ans = 0;
    if(val >= (1ll << i) * n && mx[i] >= (1ll << i)) {
        if(!i) ans++;
        else ans += dp[i - 1];
        mx[pos] += (1ll << i);
        val = min(val, mx[i]);
        ans += get(i - 1, val - (1ll << i), pos);
    }
    else ans += get(i - 1, val, pos);
    return ans;
}

long long count_tastiness(long long x, vector<long long> A) {
    while(!A.empty() && A.back() == 0) A.pop_back();
    if(A.empty()) return 1;
    n = x, k = (int)A.size();
    for(int i = 0; i < 70; i++) {
        a[i] = 0;
        dp[i] = mx[i] = 0;
    }
    for(int i = 0; i < k; i++) {
        a[i] = A[i];
    }
    vector<ll> ans = {0};
    ll sum = 0, cur = 1, cmx = 0;
    for(int i = 0; i < 61; i++) {
        int sz = (int)ans.size();
        sum += (a[i] << i);
        if((1ll << i) * n > (ll)1e18) {
            break;
        }
        if(sum - (1ll << i) * n < 0) {
            dp[i] = cur;
            mx[i] = cmx;
        }
        else {
            mx[i] = (1ll << i);
            dp[i] = cur + get(i - 1, sum - (1ll << i) * n, i);
            cur = dp[i];
            cmx = mx[i];
        }
    }
    return cur;
}