#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T SQR(T x) {
  return x * x;
}
template <typename T>
inline T MIN(T x, T y) {
  return (x < y) ? x : y;
}
template <typename T>
inline T MAX(T x, T y) {
  return (x > y) ? x : y;
}
template <typename T>
inline T ABS(T x) {
  return (x > 0) ? x : -x;
}
template <typename T>
inline void UPDATE_MIN(T &x, T y) {
  if (y < x) {
    x = y;
  }
}
template <typename T>
inline void UPDATE_MAX(T &x, T y) {
  if (x < y) {
    x = y;
  }
}
template <typename T>
inline int ARGMAX(T cont) {
  return max_element(cont.begin(), cont.end()) - cont.begin();
}
template <typename T>
inline int ARGMIN(T cont) {
  return min_element(cont.begin(), cont.end()) - cont.begin();
}
vector<string> split(const string &s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
template <typename T, typename... Args>
inline string arrStr(T arr, int n) {
  stringstream s;
  s << "[";
  for (__typeof(n - 1) i = (0), __tmpvar__end87 = (n - 1); i < __tmpvar__end87;
       i++)
    s << arr[i] << ",";
  s << arr[n - 1] << "]";
  return s.str();
}
template <class T>
inline string TOSTR(const T &x) {
  stringstream ss;
  ss << x;
  return ss.str();
}
inline int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
inline long long gcd(long long a, long long b) { return a ? gcd(b % a, a) : b; }
inline long long powmod(long long a, long long p, long long m) {
  long long r = 1;
  while (p) {
    if (p & 1) r = r * a % m;
    p >>= 1;
    a = a * a % m;
  }
  return r;
}
struct pairhash {
  template <typename T, typename U>
  std::size_t operator()(const std::pair<T, U> &x) const {
    return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  }
};
template <typename K, typename V>
V GetWithDef(const std::unordered_map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  return (it == m.end()) ? defval : it->second;
}
template <typename K, typename V>
void SetDef(std::unordered_map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  if (it == m.end()) m[key] = defval;
}
const int MOD = 1000 * 1000 * 1000 + 7;
const double PI = 3.1415926535897932384626433832795l;
inline void addto(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void subto(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
}
inline int sub(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void multo(int &a, int b) { a = (long long)a * b % MOD; }
inline int mul(int a, int b) { return (long long)a * b % MOD; }
inline int mulmod(int a, int b, int mod) { return (long long)a * b % mod; }
inline int powmod(int a, int e, int mod) {
  int x;
  for (x = 1; e > 0; e >>= 1) {
    if (e & 1) x = mulmod(x, a, mod);
    a = mulmod(a, a, mod);
  }
  return x;
}
inline int invmod(int a, int mod) { return powmod(a, mod - 2, mod); }
inline long long invmodLL(long long p) {
  long long q = p;
  for (long long a = p * p; a != 1; a *= a) q *= a;
  return q;
}
long long N, M, K, L, E;
int arr[210123] = {};
int bin[210123] = {};
int main() {
  ios_base::sync_with_stdio(0);
  scanf(
      "%lld"
      "%lld",
      &N, &K);
  for (__typeof(N + 1) i = (0), __tmpvar__end218 = (N + 1);
       i < __tmpvar__end218; i++) {
    scanf("%d", &arr[i]);
    assert(ABS(arr[i]) <= K);
  }
  long long res = 0;
  int lastbin = 0;
  for (__typeof(N + 500) i = (0), __tmpvar__end224 = (N + 500);
       i < __tmpvar__end224; i++) {
    if (i <= N)
      res += arr[i];
    else if (!res)
      break;
    1;
    lastbin = (res >= 0) ? 1 : -1;
    res >>= 1;
  }
  1;
  if (lastbin == -1) {
    for (__typeof(N + 1) i = (0), __tmpvar__end235 = (N + 1);
         i < __tmpvar__end235; i++)
      arr[i] = -arr[i];
  }
  long long cntnz = 0;
  res = 0;
  for (__typeof(N + 500) i = (0), __tmpvar__end239 = (N + 500);
       i < __tmpvar__end239; i++) {
    if (i <= N)
      res += arr[i];
    else if (!res)
      break;
    bin[i] = res & 1;
    if (res < 0) res -= bin[i];
    cntnz += ABS(bin[i]);
    1;
    res >>= 1;
  }
  long long ans = 0;
  for (__typeof(N + 1) i = (0), __tmpvar__end251 = (N + 1);
       i < __tmpvar__end251; i++) {
    long long diff = 0;
    long long pow2 = 1;
    long long cntcur = 0;
    for (__typeof(37) j = (0), __tmpvar__end255 = (37); j < __tmpvar__end255;
         j++) {
      diff += pow2 * bin[i + j];
      pow2 *= 2;
      cntcur += ABS(bin[i + j]);
    }
    if (cntcur != cntnz) continue;
    if (i == N && arr[i] == diff) continue;
    if (ABS(arr[i] - diff) <= K) {
      1;
      ans += 1;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

Limak is a little polar bear. He doesn't have many toys and thus he often plays with polynomials.

He considers a polynomial valid if its degree is n and its coefficients are integers not exceeding k by the absolute value. More formally:

Let a0, a1, ..., an denote the coefficients, so <image>. Then, a polynomial P(x) is valid if all the following conditions are satisfied:

  * ai is integer for every i; 
  * |ai| ≤ k for every i; 
  * an ≠ 0. 



Limak has recently got a valid polynomial P with coefficients a0, a1, a2, ..., an. He noticed that P(2) ≠ 0 and he wants to change it. He is going to change one coefficient to get a valid polynomial Q of degree n that Q(2) = 0. Count the number of ways to do so. You should count two ways as a distinct if coefficients of target polynoms differ.

Input

The first line contains two integers n and k (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 109) — the degree of the polynomial and the limit for absolute values of coefficients.

The second line contains n + 1 integers a0, a1, ..., an (|ai| ≤ k, an ≠ 0) — describing a valid polynomial <image>. It's guaranteed that P(2) ≠ 0.

Output

Print the number of ways to change one coefficient to get a valid polynomial Q that Q(2) = 0.

Examples

Input

3 1000000000
10 -9 -3 5


Output

3


Input

3 12
10 -9 -3 5


Output

2


Input

2 20
14 -7 19


Output

0

Note

In the first sample, we are given a polynomial P(x) = 10 - 9x - 3x2 + 5x3.

Limak can change one coefficient in three ways:

  1. He can set a0 = - 10. Then he would get Q(x) = - 10 - 9x - 3x2 + 5x3 and indeed Q(2) = - 10 - 18 - 12 + 40 = 0. 
  2. Or he can set a2 = - 8. Then Q(x) = 10 - 9x - 8x2 + 5x3 and indeed Q(2) = 10 - 18 - 32 + 40 = 0. 
  3. Or he can set a1 = - 19. Then Q(x) = 10 - 19x - 3x2 + 5x3 and indeed Q(2) = 10 - 38 - 12 + 40 = 0. 



In the second sample, we are given the same polynomial. This time though, k is equal to 12 instead of 109. Two first of ways listed above are still valid but in the third way we would get |a1| > k what is not allowed. Thus, the answer is 2 this time.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T SQR(T x) {
  return x * x;
}
template <typename T>
inline T MIN(T x, T y) {
  return (x < y) ? x : y;
}
template <typename T>
inline T MAX(T x, T y) {
  return (x > y) ? x : y;
}
template <typename T>
inline T ABS(T x) {
  return (x > 0) ? x : -x;
}
template <typename T>
inline void UPDATE_MIN(T &x, T y) {
  if (y < x) {
    x = y;
  }
}
template <typename T>
inline void UPDATE_MAX(T &x, T y) {
  if (x < y) {
    x = y;
  }
}
template <typename T>
inline int ARGMAX(T cont) {
  return max_element(cont.begin(), cont.end()) - cont.begin();
}
template <typename T>
inline int ARGMIN(T cont) {
  return min_element(cont.begin(), cont.end()) - cont.begin();
}
vector<string> split(const string &s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
template <typename T, typename... Args>
inline string arrStr(T arr, int n) {
  stringstream s;
  s << "[";
  for (__typeof(n - 1) i = (0), __tmpvar__end87 = (n - 1); i < __tmpvar__end87;
       i++)
    s << arr[i] << ",";
  s << arr[n - 1] << "]";
  return s.str();
}
template <class T>
inline string TOSTR(const T &x) {
  stringstream ss;
  ss << x;
  return ss.str();
}
inline int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
inline long long gcd(long long a, long long b) { return a ? gcd(b % a, a) : b; }
inline long long powmod(long long a, long long p, long long m) {
  long long r = 1;
  while (p) {
    if (p & 1) r = r * a % m;
    p >>= 1;
    a = a * a % m;
  }
  return r;
}
struct pairhash {
  template <typename T, typename U>
  std::size_t operator()(const std::pair<T, U> &x) const {
    return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  }
};
template <typename K, typename V>
V GetWithDef(const std::unordered_map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  return (it == m.end()) ? defval : it->second;
}
template <typename K, typename V>
void SetDef(std::unordered_map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  if (it == m.end()) m[key] = defval;
}
const int MOD = 1000 * 1000 * 1000 + 7;
const double PI = 3.1415926535897932384626433832795l;
inline void addto(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void subto(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
}
inline int sub(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void multo(int &a, int b) { a = (long long)a * b % MOD; }
inline int mul(int a, int b) { return (long long)a * b % MOD; }
inline int mulmod(int a, int b, int mod) { return (long long)a * b % mod; }
inline int powmod(int a, int e, int mod) {
  int x;
  for (x = 1; e > 0; e >>= 1) {
    if (e & 1) x = mulmod(x, a, mod);
    a = mulmod(a, a, mod);
  }
  return x;
}
inline int invmod(int a, int mod) { return powmod(a, mod - 2, mod); }
inline long long invmodLL(long long p) {
  long long q = p;
  for (long long a = p * p; a != 1; a *= a) q *= a;
  return q;
}
long long N, M, K, L, E;
int arr[210123] = {};
int bin[210123] = {};
int main() {
  ios_base::sync_with_stdio(0);
  scanf(
      "%lld"
      "%lld",
      &N, &K);
  for (__typeof(N + 1) i = (0), __tmpvar__end218 = (N + 1);
       i < __tmpvar__end218; i++) {
    scanf("%d", &arr[i]);
    assert(ABS(arr[i]) <= K);
  }
  long long res = 0;
  int lastbin = 0;
  for (__typeof(N + 500) i = (0), __tmpvar__end224 = (N + 500);
       i < __tmpvar__end224; i++) {
    if (i <= N)
      res += arr[i];
    else if (!res)
      break;
    1;
    lastbin = (res >= 0) ? 1 : -1;
    res >>= 1;
  }
  1;
  if (lastbin == -1) {
    for (__typeof(N + 1) i = (0), __tmpvar__end235 = (N + 1);
         i < __tmpvar__end235; i++)
      arr[i] = -arr[i];
  }
  long long cntnz = 0;
  res = 0;
  for (__typeof(N + 500) i = (0), __tmpvar__end239 = (N + 500);
       i < __tmpvar__end239; i++) {
    if (i <= N)
      res += arr[i];
    else if (!res)
      break;
    bin[i] = res & 1;
    if (res < 0) res -= bin[i];
    cntnz += ABS(bin[i]);
    1;
    res >>= 1;
  }
  long long ans = 0;
  for (__typeof(N + 1) i = (0), __tmpvar__end251 = (N + 1);
       i < __tmpvar__end251; i++) {
    long long diff = 0;
    long long pow2 = 1;
    long long cntcur = 0;
    for (__typeof(37) j = (0), __tmpvar__end255 = (37); j < __tmpvar__end255;
         j++) {
      diff += pow2 * bin[i + j];
      pow2 *= 2;
      cntcur += ABS(bin[i + j]);
    }
    if (cntcur != cntnz) continue;
    if (i == N && arr[i] == diff) continue;
    if (ABS(arr[i] - diff) <= K) {
      1;
      ans += 1;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

```