零

题号：NC318397
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

称一个整数序列 $a_1,a_2,\cdots,a_n$ 为零序列，当且仅当其满足如下条件：
1. 对于 $i=1,2,\cdots,n-1$ ，有 $a_i\neq a_{i+1}$ 。
2. $a_1,a_2,\cdots,a_n$ 的二进制异或和为 $0$ ，即：
$\bigoplus_{i=1}^{n}a_i=0$
给定 $n$ 和 $m$ ，求长度为 $n$ 且每个元素在 $\{0,1,2,\cdots,2^{m}-1\}$ 内选择的零序列数量。

输入描述:

第一行一个正整数  ，表示数据组数。
对于每组数据，一行两个整数  ，分别表示序列的长度和序列元素在二进制下的长度。

输出描述:

对于每组数据，一行一个整数表示答案对  取模后的结果。

示例1

输入

复制

输出

复制