У полярного медвежонка Лимака мало игрушек, поэтому он постоянно играет с многочленами (полиномами).
Он считает многочлен правильным, если тот имеет степень n и все его коэффициенты являются целыми числами не превосходящими k по абсолютному значению. Формально, пусть a0, a1, ..., an это коэффициенты многочлена 
. Тогда многочлен P(x) является правильным если выполнены следующие условия:
- ai является целым числом для всех i от 0 до n;
- |ai| ≤ k для всех i от 0 до n;
- an ≠ 0.
Лимаку недавно подарили правильный многочлен P с коэффициентами a0, a1, a2, ..., an. Он обратил внимание, что P(2) ≠ 0 и теперь хочет это исправить. Лимак хочет изменить ровно один коэффициент многочлена P, так чтобы получить правильный многочлен Q степени n, такой что Q(2) = 0. Вычислите, сколькими способами он может это сделать. Два способа следует считать различными, если коэффициенты полученных многочленов различаются.
Выходные данные
Выведите количество способов изменить ровно один коэффициент многочлена P, так чтобы получить правильный многочлен Q, для которого Q(2) = 0.
Примечание
В первом примере дан многочлен P(x) = 10 - 9x - 3x2 + 5x3.
Существуют три способа изменить коэффициенты подходящим образом:
- Установить a0 = - 10, так чтобы Q(x) = - 10 - 9x - 3x2 + 5x3. Действительно, Q(2) = - 10 - 18 - 12 + 40 = 0.
- Поменять a2 = - 8. Тогда Q(x) = 10 - 9x - 8x2 + 5x3 и Q(2) = 10 - 18 - 32 + 40 = 0.
- Последний способ — сделать a1 = - 19. Тогда Q(x) = 10 - 19x - 3x2 + 5x3 и Q(2) = 10 - 38 - 12 + 40 = 0.
Во втором примере дан тот же самый многочлен, но значение k равно 12 вместо 109. Первые два способа по прежнему работает, а в третьем получается |a1| > k и соответствующий Q не является правильным. Таким образом, ответ для этого примера равен 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1000000000
10 -9 -3 5
|
3
|
|
2
|
3 12
10 -9 -3 5
|
2
|
|
3
|
2 20
14 -7 19
|
0
|