Bobo has $n$ integers $a_1, a_2, \dots, a_n$. He would like to choose some of the integers and calculate their product (the product of the empty set is defined as $1$).
Bobo would like to know the number of products whose remainder divided by $2017$ is $r$. As the exact number is too large, he only asks for the number modulo $2$.
Input
The input contains zero or more test cases and is terminated by end-of-file. For each case,
The first line contains two integers $n, r$.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$.
- $1 \leq n \leq 2\times 10^6$
- $1 \leq r, a_1, a_2, \dots, a_n < 2017$
- The sum of $n$ does not exceed $2 \times 10^6$.
Output
For each case, output an integer which denotes the parity.
Sample Input
3 6 2 3 4 4 1 1 1 2016 2016
Sample Output
1 0