涂色

题目描述

yuno 有一个 $n \times m$ 个方格的表格。其中有 $n$ 行和 $m$ 列。刚开始表格全是没有颜色的，现在 yuno 要给这个表格的每个格子染成红色或蓝色，使表格中每个 $2 \times 2$ 的方形区域都包含 $2$ 个红色的格子。现在 yuno 想知道有多少中染色的方案数，于是她来请教 IOI 金牌的你。

输入格式

本题包含多组数据。

第一行一个整数 $T$ 表示测试数据的组数。对于每一组测试数据：

共一行，每行两个整数 $n,m$，分别表示表格的行数与列数。

输出格式

对于每一组测试数据，共一行，表示染色的方案数对于 $10^9 + 7$ 取模后得到的值。

样例 #1

样例输入 #1

1
2 2

样例输出 #1

6

样例解释 #1

六种方法如下，其中 R 表示红色，B 表示蓝色。

RR  RB  RB  BR  BR  BB
BB  BR  RB  BR  RB  RR

样例 #2

样例输入 #2

2
4 7
3 5

样例输出 #2

142
38

数据范围

对于 $100\%$ 的数据，保证 $1 \le T \le 10^4$，$2 \le n, m \le 10^9$。

提示

对于 Python 语言，你可以使用 1<<x 来代替 2**x，或者用 pow(2, x, mod)。你不需要知道原理，用就完了。这很重要！

本题输入可参考下列方式实现：

n, k, x = map(int, input().split())
a = list(map(int,input().split()))