곱은 짝수인가?

시간 제한1초메모리 제한1024 MB

요약

N개의 정수와 K가 주어질 때, 정수들의 곱이 2^K로 나누어떨어지는지 판별해 1 또는 0을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 수학, 구현
정답자: 아직 제출이 없습니다

문제

당신은 CompanyTM의 실력 있는 프로그래머입니다. 정수 $N$ 개 $x_1, \dots, x_N$ 이 주어지고, 이들의 곱 $x_1 \cdot x_2 \cdots x_N$ 이 짝수인지 묻는 문제를 받았습니다. 당신은 매우 우아한 풀이를 찾아냅니다. 그런데 상사가 과제가 바뀌었다고 알려줍니다. 이제는 곱이 $2^K$ 로 나누어떨어지는지 알아내야 합니다. 여기서 $K \geq 0$ 은 주어지는 정수입니다.

입력

첫 줄에 정수 $N$ 과 $K$ 가 주어집니다 ( $1 \leq N \leq 100000$ , $0 \leq K \leq 1000$ ). 이어서 $N$ 개의 줄에 정수 $x_i$ 가 한 개씩 주어집니다 ( $1 \leq x_i \leq 10^9$ ).

출력

곱 $x_1 \cdot x_2 \cdots x_N$ 이 $2^K$ 로 나누어떨어지면 1을, 그렇지 않으면 0을 출력합니다.

예제2

예제 1
입력
```
4 2
3
2
1
1
```
예상 출력
```
0
```
예제 2
입력
```
5 4
3
30
6
4
7
```
예상 출력
```
1
```