Binary Stirling Numbers

題目連結

第二類斯特林數 S(n, m) 表示將 n 個元素的集合劃分成 m 個非空子集的方式數量。

例如，將一個四元素集合分成兩部分，有七種方法：
{1, 2, 3} ∪ {4}，{1, 2, 4} ∪ {3}，{1, 3, 4} ∪ {2}，{2, 3, 4} ∪ {1}，
{1, 2} ∪ {3, 4}，{1, 3} ∪ {2, 4}，{1, 4} ∪ {2, 3}。

我們可以使用以下遞迴公式來計算 S(n, m) :

當 1 < m < n 時，
S(n, m) = m * S(n - 1, m) + S(n - 1, m - 1)

但你的任務稍有不同：
給定兩個整數 n 和 m，請計算 S(n, m) 的奇偶性，即 S(n, m) mod 2 的結果。

輸入的第一行是一個正整數，表示接下來有幾筆測資。
這行後面會有一個空行。
每筆測資都是一行，包含兩個整數 n 和 m ，中間以空格分隔，且滿足 1 ≤ m ≤ n ≤ 1000000000。
每兩筆測資之間也會有一個空行。

對每筆測資輸出一個整數，為 S(n, m) mod 2 的結果。
每兩筆輸出之間也應該有一個空行。

undefined