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\)