Problem G: Binary Stirling Numbers

The Stirling number of the second kind $S(n,m)$ represents the number of ways to partition a set of $n$ things into $m$ nonempty subsets. For example, there are seven ways to split a four-element set into two parts:

\begin{displaymath}\{1,2,3\}\cup \{4\},\; \{1,2,4\}\cup \{3\},\; \{1,3,4\}\cup \{2\},\; \{2,3,4\}\cup \{1\},\end{displaymath}


\begin{displaymath}\{1,2\}\cup \{3,4\},\; \{1,3\}\cup \{2,4\},\; \{1,4\}\cup \{2,3\}.\end{displaymath}

We can compute $S(n,m)$ using the recurrence,

\begin{displaymath}S(n,m) = mS(n-1,m)+S(n-1,m-1),\qquad \mbox{for integers $1<m<n$.}\end{displaymath}

but your task is slightly different: given integers $n$ and $m$, compute the parity of $S(n,m)$, i.e. $S(n,m) \bmod 2$.

Example

$S(4,2) \bmod 2 = 1$.

Problem

Write a program that reads two positive integers $n$ and $m$, computes $S(n,m) \bmod 2$, and writes the result.

Input specification

The input consists two integers $n$ and $m$ separated by a space, with $1\le m\le n\le 1000 000 000$.

Output specification

The output should be the integer $S(n,m) \bmod 2$.

Sample input

4 2

Sample output

 
1

ACM Programming Contest -- SWERC'2001 -- University of Porto, Portugal