题目描述

题目译自 PA 2016 Runda 5 Pokrycia

在无向简单图 $G=(V, E)$ 中，顶点覆盖定义为顶点集合 $S \subseteq V$ 的任意子集，使得对于每条边 $(u, v) \in E$，至少有 $u \in S$ 或 $v \in S$。顶点覆盖 $S$ 的大小即集合 $S$ 的元素数量。

对于顶点集 $V$，有多少个无向简单图，其最小顶点覆盖的大小恰好为 $k$？两个图 $G_{1}=(V, E_{1})$ 和 $G_{2}=(V, E_{2})$ 被认为是不同的，当且仅当存在两个顶点 $u, v \in V$ $(u \neq v)$，使得边 $(u, v)$ 恰好属于 $E_{1}$ 或 $E_{2}$ 中的一个。

由于答案可能是一个非常大的数字，因此只需输出该数字除以 $2$ 的余数。

输入格式

输入数据的第一行包含一个整数 $q$ $(1 \leq q \leq 2^{14})$，表示查询数量。

接下来的 $q$ 行描述各个查询。第 $i$ 行包含两个整数 $n_{i}$ 和 $k_{i}$ $(1 \leq n_{i} < 2^{14}, 0 \leq k_{i} < n_{i})$，分别表示图的顶点数量（即 $|V|=n_{i}$）和指定的最小顶点覆盖大小。

输出格式

输出应包含 $q$ 行。第 $i$ 行应为 $0$ 或 $1$，表示第 $i$ 个查询的答案。

4
3 1
5 4
5 3
57 32

0
1
1
1

• 在第一个查询中，顶点集 $V$ 的大小为 $3$。最小顶点覆盖大小为 $1$ 的简单图恰好是那些具有一条或两条边的图。不难验证，这样的图有 $6$ 个。
• 在第二个查询中，只有在 $5$ 个顶点的完全图上，最小顶点覆盖的大小为 $4$。