Arrange

There are $m$ students in a classroom, out of which $n$ of them are girls. The teacher, Mr X wants to arrange all the students in a line. X thinks that his class girls are very talkative. So he doesn't want any two girls to be together. Mr X wants to know the number of ways he can arrange these $m$ students. Help him out.

Input

The first line contains a single integer $t(1\le t\le 10^5)$, denoting the number of testcases. Each of the next $t$ lines contain two integers $m$ and $n(1<n\le m\le 10^6)$.

Output

For each test case print the answer modulo $10^9+7$ in a single line.

Examples