Binary Stirling Numbers

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

\{1, 2, 3\} \cup \{4\}, \{1, 2, 4\} \cup \{3\}, \{1, 3, 4\} \cup \{2\}, \{2, 3, 4\} \cup \{1\}

\{1, 2\} \cup \{3, 4\}, \{1, 3\} \cup \{2, 4\}, \{1, 4\} \cup \{2, 3\}.

There is a recurrence that allows calculating S(n, m) for all $n$ and $m$:

S(0, 0) = 1; S(n, 0) = 0 for n > 0; S(0, m) = 0 for m > 0;

S(n, m) = m S(n-1, m) + S(n-1, m-1) for n, m > 0.

Your task is much "simpler": given integers $n$ and $m$ such that 1 \leq m \leq n, compute the parity of S(n, m), i.e., S(n, m) \bmod 2.

For example, S(4, 2) \bmod 2 = 1.

Write a program which for each dataset:

• reads two positive integers $n$ and $m$,

• computes S(n, m) \bmod 2,

• writes the result.