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

using namespace std;
typedef long long ll;

ll dp[71];
unordered_map<ll, ll> mem[71];
ll a[71];
ll n, k;

inline ll get(int i, ll val) {
    if(i >= k && val < n || dp[i] > val) return 1;
    if(mem[i].count(val)) return mem[i][val];
    ll ans = get(i + 1, a[i + 1] + val / 2);
    if(val >= n) {
        ans += get(i + 1, a[i + 1] + (val - n) / 2);
    }
    return mem[i][val] = 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] = 0;
        mem[i].clear();
    }
    for(int i = 0; i < k; i++) {
        a[i] = A[i];
    }
    for(int i = 0; i < 70; i++) {
        if(a[i] > n) {
            ll st = a[i];
            if(n % 2 != a[i] % 2) a[i] = n + 1;
            else a[i] = n;
            a[i + 1] += (st - a[i]) / 2;
        }
    }
    for(int i = 60; i >= 0; i--) {
        dp[i] = 2e18;
        for(ll l = 0, r = 1e18; l <= r;) {
            ll mid = (l + r) >> 1;
            if(mid >= n || a[i + 1] + mid / 2 >= dp[i + 1]) {
                dp[i] = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
    }
    return get(0, a[0]);
}