T566560 「PA Mashup #1」覆盖

简单无向图 $G=(V,E)$ 的**点覆盖**是一个点集 $S\subseteq V$，使得 $\forall (u,v)\in E$，都有 $u\in S$ 或 $v\in S$。点覆盖 $S$ 的**大小**定义为 $|S|$。 给定点集 $V$ 和整数 $k$，求出有多少张以 $V$ 为点集的简单无向图 $G$ 的最小点覆盖大小为 $k$。 两张图 $G_1=(V,E_1)$ 和 $G_2=(V,E_2)$ 不同，当且仅当存在 $u,v\in V$，使得 $(u,v)$ 只属于 $E_1$ 或 $E_2$。 给定正整数 $n$，点集 $V=\{1,2,\ldots,n\}$。 由于答案可能很大，所以只需要输出答案模 $\textcolor{red}{\textbf{2}}$ 后的余数。

**本题单个测试点内有多组测试数据。** 第一行一个正整数 $T$，表示测试数据组数。 接下来描述 $T$ 组测试数据： 每组测试数据只有一行两个整数 $n,k$，表示一次询问。$V=\{1,2,\ldots,n\}$。

输出 $T$ 行，每行一个非负整数，表示答案模 $\textcolor{red}{\textbf{2}}$ 后的余数。

#### 样例解释 - 第一组测试数据中，$n=3,k=1$。符合条件的图要么只有一条边，要么有两条边，且这两条边共用一个顶点。不难验证，原始答案为 $6$。 - 第二组测试数据中，$n=5,k=4$。不难验证符合条件的图只有完全图。 #### 数据范围 - $1\le T\le 2^{14}$； - $1\le n\lt 2^{14}$； - $0\le k\lt n$。