Limak 是一只小北极熊。他没有很多玩具,因此他经常玩多项式。
如果多项式的次数为 n 并且其系数是绝对值不超过 k 的整数,则他认为多项式有效。更正式地说:
设 a0, a1, ..., an 表示系数,因此 $$P(x) = \sum_{i=0}^{n} a_i \cdot x^i$$。那么,如果满足以下所有条件,则多项式 P(x) 有效:
- ai 是每个 i 的整数;
- |ai| 对于每个 i ≤ k;
- an ≠ 0。
Limak 最近得到了一个有效的多项式 P,其系数为 a0、a1、a2、...、an。他注意到 P(2) ≠ 0,他想改变它。他将改变一个系数以获得一个有效的 n 次多项式 Q,即 Q(2) = 0。数一下这样做的方法的数量。如果目标多项式的系数不同,则应将两种方法视为不同的方法。
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 109) - 多项式的次数和系数绝对值的限制。
第二行包含 n + 1 个整数 a0, a1, ..., an (|ai| ≤ k, an ≠ 0) - 描述有效多项式 $$P(x) = \sum_{i=0}^{n} a_i \cdot x^i$$。保证 P(2) ≠ 0。
输出
打印更改一个系数以获得 Q(2) = 0 的有效多项式 Q 的方法数。
示例
输入 #1
3 1000000000 10 -9 -3 5
输出 #1
3
输入 #2
3 12 10 -9 -3 5
输出 #2
2
输入 #3
2 20 14 -7 19
输出 #3
0
注意
在第一个示例中,我们得到一个多项式 P(x) = 10 - 9x - 3x2 + 5x3。
Limak 可以通过三种方式更改一个系数:
1.他可以设置a0 = - 10,然后他会得到Q(x) = - 10 - 9x - 3x2 + 5x3,并且确实Q(2) = - 10 - 18 - 12 + 40 = 0。
2.或者他可以设置a2 = - 8.然后Q(x) = 10 - 9x - 8x2 + 5x3 Q(2) = 10 - 18 - 32 + 40 = 0。
3.或者他可以设置a1 = - 19.然后Q(x) = 10 - 19x - 3x2 + 5x3 Q(2) = 10 - 38 - 12 + 40 = 0。
在第二个示例中,我们给出了相同的多项式。但这一次,k 等于 12,而不是 109。上面列出的两种方法仍然有效,但在第三种方法中,我们会得到 |a1| > k 什么是不允许的。因此,这次的答案是2。