天才程序员菜哭武、张老师和石头三个人已经厌倦了N皇后问题。他们在一个n*m的棋盘上玩三人象棋。经过一番激烈的拼杀，最后只剩下三个国王。
在这个n*m的棋盘上要放置三个国王，国王之间不能互相攻击。国王之间没有区别。国王的攻击范围为切比雪夫距离1以内的格子，即假设一个国王的位置是(r,c)，那么可以攻击到所有 max(|r-i|, |c-j|)=1 的位置(i,j)，而且不能有多个国王放置在同一个格子当中。
菜哭武很快发现了怎么计算有多少种放置方法，但是他太懒了，想让你帮他算。你只需要输出方案数对1,000,000,007取模的结果即可。
输入描述:
第一行两个整数t，表示有t组数据(1≤t≤105)
接下来t行，每行两个整数n,m（1<=n,m<=109），表示棋盘的长和宽
输出描述:
对于每一组数据，输出一个整数，表示放置方案数对1,000,000,007取模的结果