SCUSA Region ICPC Masthead ACM Balloon Logo
2017 ACM ICPC South Central USA Regional Programming Contest

E - Hopscotch

You’re playing hopscotch! You start at the origin and your goal is to hop to the lattice point (N, N). A hop consists of going from lattice point (x1 , y1) to (x2, y2), where x1 < x2 and y1 < y2.

You dislike making small hops though. You’ve decided that for every hop you make between two lattice points, the x-coordinate must increase by at least X and the y-coordinate must increase by at least Y.

Compute the number of distinct paths you can take between (0, 0) and (N, N) that respect the above constraints.

Two paths are distinct if there is some lattice point that you visit in one path which you don’t visit in the other. Hint: The output involves arithmetic mod 10^9 + 7. Note that with p a prime like 10^9 + 7, and x an integer not equal to 0 mod p, then x(x^(p−2)) mod p equals 1 mod p.


The first line of input designates the number of test cases. What follows are lines consisting of three integers: N, X, Y. You may assume 1 ≤ X, Y ≤ N ≤ 10^6.


The number of distinct paths you can take between the two lattice points can be very large. Hence output this number modulo 1000000007 (10^9 + 7).

Sample Input

2 1 1 
7 2 3

Sample Output