문제

(주) 회사의 수석 프로그래머인 당신에게 아래의 문제가 주어졌습니다. N개의 정수 리스트 x₁, ..., x_N이 주어질 때, 그 곱인 x₁ * x₂ ... x_N는 짝수입니까? 책의 여러 기법을 이용해 문제와 끈덕지게 씨름한 당신은 매우 우아한 해결책을 찾아냈습니다. 그런데 하... 이제야  관리 직책이 문제가 바뀐 것을 알려줬습니다! 높으신 분들은 곱 x₁ * x₂ ... x_N가 어떤 정수 K >= 0에 대해 2^K로 나누어 떨어지는지 알고 싶어 합니다.

쉴 틈이 없군요!

입력

두 정수 N, K가 주어집니다. (1 <= N <= 100000이고 0 <= K <= 1000) 이후 N개의 각 줄에 곱을 이루는 하나의 값 x₁, ..., x_N이 주어집니다. (1 <= i <= N에 대해 1 <= x_i <= 10⁹입니다.)

출력

만약 x₁ * x₂ ... x_N이 2^K로 나누어 떨어지면 1, 그 외의 경우 0을 출력합니다.