There is a wonderful country where people like eating very much. Each person has exactly one direct follower while the follower's follower is also follower of this man (of course the most unattractive man doesn't have his follower).
And you find some amazing cake, if you give it to a person, you can have the trust of this person and all his followers.
Now you want to give out M cakes randomly to N person (each person can get at most one cake), please calculate the expectation of the trust you have earned.
Because the answer can write as a / b, please output a * b^-1 mod 10^9 + 7. (b * b^-1 ≡ 1 mod 10^9 + 7)
First line a single integer T indicating the number of cases. T<=1000000;
For each case, first line two number N and M described before. N, M<=1000000;
A single integer indicating the expectation of the trust you have earned. (mod 1e9 + 7)
2 3 3 3 2
3 666666674