Is It Even?

Time limit1sMemory limit1024 MB

Summary

Given N integers and K, decide whether the product of the integers is divisible by 2^K, printing 1 or 0.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

You are a leading programmer at CompanyTM. You are given $N$ integers $x_1, \dots, x_N$ and asked whether their product $x_1 \cdot x_2 \cdots x_N$ is even. You find a very elegant solution. Then your supervisor tells you the task has changed: now you must find out whether the product is divisible by $2^K$ , where $K \geq 0$ is a given integer.

Input

The first line contains two integers $N$ and $K$ ( $1 \leq N \leq 100000$ , $0 \leq K \leq 1000$ ). The next $N$ lines each contain one integer $x_i$ ( $1 \leq x_i \leq 10^9$ ).

Output

Print 1 if $2^K$ divides $x_1 \cdot x_2 \cdots x_N$ . Otherwise, print 0.

Examples2

Example 1
Input
```
4 2
3
2
1
1
```
Expected output
```
0
```
Example 2
Input
```
5 4
3
30
6
4
7
```
Expected output
```
1
```