CF639C.Bear and Polynomials

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 _a_0, _a_1, ..., a__n denote the coefficients, so . Then, a polynomial P(x) is valid if all the following conditions are satisfied:

• a__i is integer for every i;
• |a__i| ≤ k for every i;
• a__n ≠ 0.

Limak has recently got a valid polynomial P with coefficients _a_0, _a_1, _a_2, ..., a__n. 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.

Limak 是一只小北极熊。他没有太多玩具，因此经常玩多项式。

他将一个多项式称为有效多项式，当且仅当它的次数为 $ n $，且所有系数均为绝对值不超过 $ k $ 的整数。更形式化地：

设 $ a_0, a_1, \dots, a_n $ 表示该多项式的各项系数，即 。那么，多项式 $ P(x) $ 是有效的，当且仅当满足以下全部条件：

• 对每个 $ i $，$ a_i $ 是整数；
• 对每个 $ i $，$ |a_i| \leq k $；
• $ a_n \neq 0 $。

Limak 最近得到了一个有效多项式 $ P $，其系数为 $ a_0, a_1, a_2, \dots, a_n $。他注意到 $ P(2) \neq 0 $，并希望改变它。他打算恰好修改一个系数，从而得到一个新的有效多项式 $ Q $（仍为 $ n $ 次），使得 $ Q(2) = 0 $。请计算可行的修改方式总数。若两个目标多项式的系数不同，则视为两种不同的方式。

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 _a_0, _a_1, ..., a__n (|a__i| ≤ k, a__n ≠ 0) — describing a valid polynomial . It's guaranteed that P(2) ≠ 0.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 200\,000$，$1 \leq k \leq 10^9$）—— 分别表示多项式的次数以及系数绝对值的上限。

第二行包含 $n+1$ 个整数 $a_0, a_1, \dots, a_n$（$|a_i| \leq k$，且 $a_n \neq 0$）—— 描述一个合法的多项式 。保证 $P(2) \neq 0$。

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

输出将一个系数修改为得到满足 $ Q(2) = 0 $ 的有效多项式 $ Q $ 的方案数。

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

Limak can change one coefficient in three ways:

1. He can set a_0 =  - 10. Then he would get Q(x) =  - 10 - 9_x - 3_x_2 + 5_x_3 and indeed Q(2) =  - 10 - 18 - 12 + 40 = 0.
2. Or he can set a_2 =  - 8. Then Q(x) = 10 - 9_x - 8_x_2 + 5_x_3 and indeed Q(2) = 10 - 18 - 32 + 40 = 0.
3. Or he can set a_1 =  - 19. Then Q(x) = 10 - 19_x - 3_x_2 + 5_x_3 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 |_a_1| > k what is not allowed. Thus, the answer is 2 this time.

在第一个样例中，我们给定一个多项式 $P(x) = 10 - 9x - 3x^2 + 5x^3$。

Limak 可以通过三种方式修改一个系数：

1. 他可以令 $a_0 = -10$。此时得到 $Q(x) = -10 - 9x - 3x^2 + 5x^3$，且确实有 $Q(2) = -10 - 18 - 12 + 40 = 0$。
2. 或者他可以令 $a_2 = -8$。此时 $Q(x) = 10 - 9x - 8x^2 + 5x^3$，且确实有 $Q(2) = 10 - 18 - 32 + 40 = 0$。
3. 或者他可以令 $a_1 = -19$。此时 $Q(x) = 10 - 19x - 3x^2 + 5x^3$，且确实有 $Q(2) = 10 - 38 - 12 + 40 = 0$。

在第二个样例中，我们给出的是同一个多项式。但此时 $k = 12$，而非 $109$。上述前两种修改方式仍然合法，但在第三种方式中，我们会得到 $|a_1| > k$，这是不允许的。因此，此时答案为 $2$。