问题1164--three kingdom

1164: three kingdom

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MB

题目描述

天才程序员菜哭武、张老师和石头三个人已经厌倦了N皇后问题。他们在一个n*m的棋盘上玩三人象棋。经过一番激烈的拼杀,最后只剩下三个国王。
在这个n*m的棋盘上要放置三个国王,国王之间不能互相攻击。国王之间没有区别。菜哭武很快发现了怎么计算有多少种放置方法,但是他太懒了,想让你帮他算。国王的攻击范围为切比雪夫距离1以内的格子,即假设一个国王的位置是(r,c),那么可以攻击到所有 max(|r-i|, |c-j|)=1 的位置(i,j),而且不能有多个国王放置在同一个格子当中。

输入

第一行两个整数t,表示有t组数据(1≤t≤105)
接下来t行,每行两个整数n,m(1<=n,m<=109),表示棋盘的长和宽

输出

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

样例输入 Copy

3
2 2
3 3
4 4

样例输出 Copy

0
8
140

来源/分类