#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
const int mod = (int)1e9 + 7;
int a[800400], n;
long long k;
int b[800400];
int mxn = 400000;
int main() {
  cin >> n >> k;
  for (int i = 0; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i <= n; i++) {
    b[i] = a[i];
  }
  vector<int> v2, v1;
  for (int i = 0; i <= n; i++) {
    b[i + 1] += b[i] / 2;
    int x = abs(b[i]);
    if (x % 2 == 0) {
      b[i] = 0;
    } else if (b[i] < 0) {
      b[i] = -1;
    } else
      b[i] = 1;
  }
  int m = n;
  n++;
  while (b[n] != 0) {
    b[n + 1] += b[n] / 2;
    int x = abs(b[n]);
    if (x % 2 == 0) {
      b[n] = 0;
    } else if (b[n] < 0) {
      b[n] = -1;
    } else
      b[n] = 1;
    n++;
  }
  for (int i = 0; i < n; i++) {
    if (b[i] == 1)
      v1.push_back(i);
    else if (b[i] == -1)
      v2.push_back(i);
  }
  if (v1.size() == 0 || (v2.size() > 0 && v2.back() > v1.back())) {
    for (int i = 0; i <= m; i++) a[i] *= -1;
    for (int i = 0; i < n; i++) b[i] *= -1;
    v1.clear();
    v2.clear();
    for (int i = 0; i < n; i++) {
      if (b[i] == 1)
        v1.push_back(i);
      else if (b[i] == -1)
        v2.push_back(i);
    }
  }
  int x1 = 0, x2 = 0;
  vector<int> v;
  while (x1 < v1.size() && x2 < v2.size()) {
    if (v1[x1] < v2[x2]) {
      while (x1 < v1.size() && v1[x1] < v2[x2]) {
        v.push_back(v1[x1]);
        x1++;
      }
    } else {
      int j = x2;
      while (x2 < v2.size() && v1[x1] > v2[x2]) x2++;
      int st = j + 1;
      v.push_back(v2[j]);
      for (int i = v2[j] + 1; i < v1[x1]; i++) {
        if (st < v2.size() && v2[st] == i) {
          st++;
          continue;
        }
        v.push_back(i);
      }
      x1++;
    }
  }
  while (x1 < v1.size()) {
    v.push_back(v1[x1]);
    x1++;
  }
  int ind = v[0];
  int la = v.back();
  long long ans = 0;
  for (int i = 0; i <= min(ind, m); i++) {
    if (la - i > 40) continue;
    long long cur = 0;
    for (int j = 0; j < v.size(); j++) {
      cur += (1ll << (v[j] - i));
    }
    cur -= a[i];
    if (cur < 0) cur *= -1;
    if (cur <= k) {
      if (i == m && cur == 0) continue;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

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;
const int inf = (int)1e9;
const int mod = (int)1e9 + 7;
int a[800400], n;
long long k;
int b[800400];
int mxn = 400000;
int main() {
  cin >> n >> k;
  for (int i = 0; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i <= n; i++) {
    b[i] = a[i];
  }
  vector<int> v2, v1;
  for (int i = 0; i <= n; i++) {
    b[i + 1] += b[i] / 2;
    int x = abs(b[i]);
    if (x % 2 == 0) {
      b[i] = 0;
    } else if (b[i] < 0) {
      b[i] = -1;
    } else
      b[i] = 1;
  }
  int m = n;
  n++;
  while (b[n] != 0) {
    b[n + 1] += b[n] / 2;
    int x = abs(b[n]);
    if (x % 2 == 0) {
      b[n] = 0;
    } else if (b[n] < 0) {
      b[n] = -1;
    } else
      b[n] = 1;
    n++;
  }
  for (int i = 0; i < n; i++) {
    if (b[i] == 1)
      v1.push_back(i);
    else if (b[i] == -1)
      v2.push_back(i);
  }
  if (v1.size() == 0 || (v2.size() > 0 && v2.back() > v1.back())) {
    for (int i = 0; i <= m; i++) a[i] *= -1;
    for (int i = 0; i < n; i++) b[i] *= -1;
    v1.clear();
    v2.clear();
    for (int i = 0; i < n; i++) {
      if (b[i] == 1)
        v1.push_back(i);
      else if (b[i] == -1)
        v2.push_back(i);
    }
  }
  int x1 = 0, x2 = 0;
  vector<int> v;
  while (x1 < v1.size() && x2 < v2.size()) {
    if (v1[x1] < v2[x2]) {
      while (x1 < v1.size() && v1[x1] < v2[x2]) {
        v.push_back(v1[x1]);
        x1++;
      }
    } else {
      int j = x2;
      while (x2 < v2.size() && v1[x1] > v2[x2]) x2++;
      int st = j + 1;
      v.push_back(v2[j]);
      for (int i = v2[j] + 1; i < v1[x1]; i++) {
        if (st < v2.size() && v2[st] == i) {
          st++;
          continue;
        }
        v.push_back(i);
      }
      x1++;
    }
  }
  while (x1 < v1.size()) {
    v.push_back(v1[x1]);
    x1++;
  }
  int ind = v[0];
  int la = v.back();
  long long ans = 0;
  for (int i = 0; i <= min(ind, m); i++) {
    if (la - i > 40) continue;
    long long cur = 0;
    for (int j = 0; j < v.size(); j++) {
      cur += (1ll << (v[j] - i));
    }
    cur -= a[i];
    if (cur < 0) cur *= -1;
    if (cur <= k) {
      if (i == m && cur == 0) continue;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

```