P14654 夤生月

小 L 给你出了一道简单数学题。 对于一个长度为 $n$ 的排列 $p_n$，我们在 $i$ 与 $p_i$ 之间连无向边，设形成的连通块个数为 $C(p_n)$。 对于一个连通块 $S$，如果他包含的点的编号为 $x_1,x_2\dots x_k$，那么他的权值为 $w(S)=\sum\limits_{i=1}^k 2^{x_i}$。 如果连通块分别为 $S_1,S_2\dots S_{C(p_n)}$，那么记该排列的权值为 $\sum\limits_{i=1}^{C(p_n)}2^{w(S_i)}$。 记 $F(n,m)$ 表示 $C(p_n)=m$ 的 $p_n$ 个数。 记 $G(n,m)$ 为 $C(p_n)=m$ 的 $p_n$ 的不同权值数量。 这里认为 $F(0,0)=G(0,0)=1$。 现在有 $Q$ 次询问，每次给出 $op,n,m$： - 如果 $op=1$，你需要输出 $F(n,m)\bmod 2$。 - 如果 $op=2$，你需要输出 $G(n,m)\bmod 2$。

第一行一个整数 $Q$ 代表询问次数。 接下来 $Q$ 行，每行三个整数 $op,n,m$ 代表小 L 的一次询问。 - 如果 $op=1$，你需要输出 $F(n,m)\bmod 2$。 - 如果 $op=2$，你需要输出 $G(n,m)\bmod 2$。

一行一个长度为 $Q$ 的 $01$ 字符串代表答案序列。

- 对于 $20\%$ 的数据，$0\leq n,m\leq 10$。 - 对于 $40\%$ 的数据，$0\leq n,m\leq 5000$。 - 对于另外 $15\%$ 的数据，$op=1$。 - 对于另外 $15\%$ 的数据，$op=2$。 - 对于另外 $15\%$ 的数据，$0\leq n,m\leq 10^5$。 - 对于 $100\%$ 的数据，$1\leq Q\leq 10^6,0\leq n,m\leq 10^9,1\leq op\leq 2$。