开车

开车

Description

你在一个\(n × m\)的网格图里开一辆奇怪的车,初始你在\((0, 0)\)点,每一时刻你有三种选择,分别是
1. 按下车上的A按钮,会使得你向右走一格,也就是从\((i, j)\)走到\((i + 1, j)\)
2. 按下车上的B按钮,也会使得你向右走一格,即从\((i, j)\)走到\((i + 1, j)\)
3. 按下车上的C按钮,会使得你向右上走一格,即从\((i, j)\)走到\((i + 1, j + 1)\)
你想知道从\((0, 0)\)走到\((n, m)\)有多少种不同的开车方式。 两种开车方式不同当且仅当存在某一时刻,两种方式采取了不同的操作。

Format

Input

多组数据,第一行是数据组数 \(T\)
\(T\) 行,每行两个数, \(n\) 和 \(m\),意义如题目描述。

Output

\(T\) 行, 每行一个数,表示方法数,答案对\((10^9 + 7)\)取模

Sample

Input

1
3 2

Output

6

Limitation

\(30\%: 1 ≤ n, m ≤ 100\)
\(50\%: 1 ≤ n, m ≤ 1000\)
\(100\%: 1 ≤ n, m ≤ 10^6, 1 ≤ T ≤ 100\)

信息

ID
1013
难度
4
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者