问题描述

天才程序员菜哭武、张老师和石头三个人已经厌倦了 N 皇后问题。他们在一个 $n \times m$ 的棋盘上玩三人象棋。经过一番激烈的拼杀，最后只剩下三个国王。

在这个 $n \times m$ 的棋盘上要放置三个国王，国王之间不能互相攻击。国王之间没有区别。菜哭武很快发现了怎么计算有多少种放置方法，但是他太懒了，想让你帮他算。国王的攻击范围为切比雪夫距离 $1$ 以内的格子，即假设一个国王的位置是 $(r, c)$，那么可以攻击到所有 $\max(|r-i|, |c-j|)=1$ 的位置 $(i, j)$，而且不能有多个国王放置在同一个格子当中。

输入格式

第一行两个整数 $t$，表示有 $t$ 组数据 $(1 \leq t \leq 10^5)$。

接下来 $t$ 行，每行两个整数 $n, m$（$1 \leq n, m \leq 10^9$），表示棋盘的长和宽。

输出格式

对于每一组数据，输出一个整数，表示放置方案数对 $1,000,000,007$ 取模的结果。

样例输入

3
2 2
3 3
4 4

样例输出

0
8
140