Bob 喜欢给网格涂色。今天，他想把一个 $n \times m$ 网格中的每个格子都涂成黑色或白色。Bob 认为，如果没有任何三个连续的格子颜色相同（无论是在水平、垂直还是对角线方向上），那么这种涂色方式就是“美丽的”。以下是一些示例以帮助你理解：
(1)、(2)、(4) 不是美丽的，而 (3)、(5) 是美丽的。
现在问题来了：给定 $n$ 和 $m$，你能告诉 Bob 有多少种美丽的涂色方式吗？设答案为 $x$，你只需要输出 $x \pmod{1\,000\,000\,007}$。
输入格式
第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示查询的数量。 接下来的 $T$ 行，每行包含两个整数 $n, m$ ($1 \le n, m \le 10^9$)，表示一个查询。
输出格式
对于每个查询，输出一行答案。
样例
输入 1
6 1 1 2 2 2 3 3 3 3 4 4 4
输出 1
2 16 36 32 44 18