#include <bits/stdc++.h>
template <typename T>
class IntegerIterator
    : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
 public:
  explicit IntegerIterator(int value) : value(value) {}
  IntegerIterator& operator++() {
    ++value;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value;
    return copy;
  }
  IntegerIterator& operator--() {
    --value;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value;
    return copy;
  }
  T operator*() const { return value; }
  bool operator==(IntegerIterator rhs) { return value == rhs.value; }
  bool operator!=(IntegerIterator rhs) { return !(*this == rhs); }

 private:
  T value;
};
template <typename T>
class IntegerRange {
 public:
  IntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IntegerIterator<T> begin() const { return IntegerIterator<T>(begin_); }
  IntegerIterator<T> end() const { return IntegerIterator<T>(end_); }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedIntegerRange {
 public:
  ReversedIntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  std::reverse_iterator<IntegerIterator<T>> begin() const {
    return std::reverse_iterator<IntegerIterator<T>>(
        IntegerIterator<T>(begin_));
  }
  std::reverse_iterator<IntegerIterator<T>> end() const {
    return std::reverse_iterator<IntegerIterator<T>>(IntegerIterator<T>(end_));
  }

 private:
  T begin_;
  T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
  return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
  return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
  return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  return ReversedIntegerRange<T>(from + 1, to);
}
using namespace std;
class TaskC {
 public:
  int64_t k;
  void solve(std::istream& in, std::ostream& out) {
    int n;
    in >> n >> k;
    ++n;
    vector<int64_t> values(n);
    for (int i : range(n)) {
      in >> values[i];
    }
    for (int j : range(2)) {
      if (try_solve(values, out)) {
        return;
      }
      for (int i : range(values.size())) {
        values[i] = -values[i];
      }
    }
  }
  bool try_solve(vector<int64_t> values, std::ostream& out) {
    int n = (int)values.size();
    vector<int64_t> v((unsigned long)(n + 120));
    for (int i : range(n)) {
      for (int j : range(32)) {
        if (values[i] > 0) {
          if ((1LL << j) & values[i]) {
            ++v[i + j];
          }
        } else {
          if ((1LL << j) & (-values[i])) {
            --v[i + j];
          }
        }
      }
    }
    int64_t carry = 0;
    for (size_t i : range(v.size())) {
      int64_t cur = carry + v[i];
      carry = cur / 2;
      v[i] = int(cur % 2);
      if (v[i] == -1) {
        --carry;
        v[i] = 1;
      }
      assert(v[i] == 0 || v[i] == 1);
    }
    if (carry < 0) {
      return false;
    }
    assert(!carry);
    int mx = -1;
    for (int i : range(v.size())) {
      if (v[i]) {
        mx = i;
      }
    }
    assert(mx != -1);
    int answer = 0;
    for (size_t i : range(values.size())) {
      if (mx - i > 32) {
        if (v[i]) {
          out << answer;
          return true;
        }
        continue;
      }
      int64_t need_subtract = 0;
      for (int j : range(33)) {
        need_subtract += ((1LL * v[i + j]) << j);
      }
      if (values[i] - need_subtract >= -k) {
        if (i != n - 1 || values[i] - need_subtract != 0) ++answer;
      }
      if (v[i]) {
        out << answer;
        return true;
      }
    }
    out << answer;
    return true;
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  TaskC solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(0);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}

### Prompt

In Cpp, your task is to solve 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>
template <typename T>
class IntegerIterator
    : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
 public:
  explicit IntegerIterator(int value) : value(value) {}
  IntegerIterator& operator++() {
    ++value;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value;
    return copy;
  }
  IntegerIterator& operator--() {
    --value;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value;
    return copy;
  }
  T operator*() const { return value; }
  bool operator==(IntegerIterator rhs) { return value == rhs.value; }
  bool operator!=(IntegerIterator rhs) { return !(*this == rhs); }

 private:
  T value;
};
template <typename T>
class IntegerRange {
 public:
  IntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IntegerIterator<T> begin() const { return IntegerIterator<T>(begin_); }
  IntegerIterator<T> end() const { return IntegerIterator<T>(end_); }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedIntegerRange {
 public:
  ReversedIntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  std::reverse_iterator<IntegerIterator<T>> begin() const {
    return std::reverse_iterator<IntegerIterator<T>>(
        IntegerIterator<T>(begin_));
  }
  std::reverse_iterator<IntegerIterator<T>> end() const {
    return std::reverse_iterator<IntegerIterator<T>>(IntegerIterator<T>(end_));
  }

 private:
  T begin_;
  T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
  return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
  return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
  return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  return ReversedIntegerRange<T>(from + 1, to);
}
using namespace std;
class TaskC {
 public:
  int64_t k;
  void solve(std::istream& in, std::ostream& out) {
    int n;
    in >> n >> k;
    ++n;
    vector<int64_t> values(n);
    for (int i : range(n)) {
      in >> values[i];
    }
    for (int j : range(2)) {
      if (try_solve(values, out)) {
        return;
      }
      for (int i : range(values.size())) {
        values[i] = -values[i];
      }
    }
  }
  bool try_solve(vector<int64_t> values, std::ostream& out) {
    int n = (int)values.size();
    vector<int64_t> v((unsigned long)(n + 120));
    for (int i : range(n)) {
      for (int j : range(32)) {
        if (values[i] > 0) {
          if ((1LL << j) & values[i]) {
            ++v[i + j];
          }
        } else {
          if ((1LL << j) & (-values[i])) {
            --v[i + j];
          }
        }
      }
    }
    int64_t carry = 0;
    for (size_t i : range(v.size())) {
      int64_t cur = carry + v[i];
      carry = cur / 2;
      v[i] = int(cur % 2);
      if (v[i] == -1) {
        --carry;
        v[i] = 1;
      }
      assert(v[i] == 0 || v[i] == 1);
    }
    if (carry < 0) {
      return false;
    }
    assert(!carry);
    int mx = -1;
    for (int i : range(v.size())) {
      if (v[i]) {
        mx = i;
      }
    }
    assert(mx != -1);
    int answer = 0;
    for (size_t i : range(values.size())) {
      if (mx - i > 32) {
        if (v[i]) {
          out << answer;
          return true;
        }
        continue;
      }
      int64_t need_subtract = 0;
      for (int j : range(33)) {
        need_subtract += ((1LL * v[i + j]) << j);
      }
      if (values[i] - need_subtract >= -k) {
        if (i != n - 1 || values[i] - need_subtract != 0) ++answer;
      }
      if (v[i]) {
        out << answer;
        return true;
      }
    }
    out << answer;
    return true;
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  TaskC solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(0);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}

```