# Problem E

Is It Even?

You are a leading programmer at $\text {Company}^\text {TM}$, and have
been given the following task. Given a list of $N$ integers $x_1,\ldots , x_ N$, is their product
$x_1\cdot x_2 \cdot \ldots \cdot
x_ N$ even? You plug away at the problem using every
trick in the book, and come up with a very elegant solution. Lo
and behold, your supervisor *then* informs
you that the task has changed! It turns out the higher ups want
you to find out if the product $x_1 \cdot x_2 \cdot \ldots \cdot x_
N$ is divisible by $2^
K$ for some integer $K
\geq 0$.

You just can’t catch a break!

## Input

The input consists of two integers $N, K$ $(1 \leq N \leq 100\, 000$ and $0 \leq K \leq 1000$). These are followed by $N$ lines, each with a single value $x_1,\ldots , x_ N$ respectively ($1 \leq x_ i \leq 10^9$ for each $1 \leq i \leq N$) which form the product.

## Output

Display `1` if $2^ K$ divides $x_1\cdot x_2 \cdot \ldots \cdot x_
N$, otherwise display `0`.

Sample Input 1 | Sample Output 1 |
---|---|

4 2 3 2 1 1 |
0 |

Sample Input 2 | Sample Output 2 |
---|---|

5 4 3 30 6 4 7 |
1 |