WD与矩阵

题目背景

WD整日沉浸在矩阵中,无法自拔……

题目描述

WD 特别喜欢矩阵,尤其是 01 矩阵。 一天,CX 给了 WD 一个巨大的 $n$ 行 $m$ 列的 01 矩阵,WD 发现这个矩阵每行、每列的异或值都是 0。 CX 随后就问道:“WD,你知道有多少 01 矩阵每行每列异或值都是 0 吗!?”WD 当然不会这个问题,于是他来请教你。 由于答案可能很大,输出结果模 $998\,244\,353$ 的值即可。

输入输出格式

输入格式


第一行一个数 $T$,表示数据组数。 接下来 $T$ 行每行两个数 $n,m$,分别表示询问的行数和列数。

输出格式


共 $T$ 行,每行一个数,表示答案对 $998\,244\,353$ 取模的结果。

输入输出样例

输入样例 #1

2
2 2
2 2018

输出样例 #1

2
851481696

说明

- subtask1(11pts):$1\le T\le 10,~1\le n,m\le 4$ - subtask2(43pts):$1\le T\le 5,~1\le n\le 5,~1\le m\le 1,000$ - subtask3(46pts):$1\le T\le 10^5,~1\le n,m\le 10^9$