Ở một thế giới song song khác, ANT MAN sẽ chính là người ngăn chặn THANOS có 6 viên đá vô cực.

Biết rằng thế giới Marvel nói trên được biễu diễn thành hệ trục tọa độ \(Oxy\).

ANT MAN đang ở ô \((1,1)\) sẽ đi đến ô \((n,m)\) - THANOS is here.

Biết rằng nếu ANT MAN đang ở ô \((x,y)\) thì ANT MAN có thể đi đến \(1\) trong \(2\) ô \((x + 1,y)\) và \((x,y+1)\).

Doctor Strange nói rằng "Số khả năng chúng ta dành chiến thắng chính là số đường đi của ANT MAN đến THANOS"

Hãy tìm số khả năng đội Avenger dành chiến thắng.

Input

• \(t(t \le 10^3)\) - số test
• mỗi test có \(2\) số nguyên dương \(n,m (1 \le n,m \le 10^6)\)

Output

• Số khả năng dành chiến thắng % \((10^9 +7)\)

Example

1
2 3  

3