2.3 Parking Wars

Score: 100pts

Time Limit: 1.00 sec

An international conference is being held in one of the countries on Codeland. One member from each country is attending the conference. A total of \(N\) delegates are attending the conference. There are \(M\) nations involved in a dispute. For the conference, the members reach the conference hall in a car and there is a valet parking system to make it easy for the delegates. You have to park the cars in such a way that no cars of any of the delegates of the countries involved in the dispute are parked adjacent to each other. You have to output the number of ways in which you can achieve this. Since the answer can be very large you have to output the result as (result%p) where p is \(10^{9} + 7\). It is guaranteed that there is an answer possible for all test cases.

Constraints

\(1 \leq t \leq 1000 \)

\(2 \leq N \leq 10000\)

\(2 \leq M \leq 5000\)

\(2 \leq N \leq 10000\)

\(2 \leq M \leq 5000\)

Input Format

The first line will contain a single integer \(t\), which denotes the number of test cases.

Each of the next t lines contains two integers, \(N\), \(M\), which are separated by a space.

\(N\) represents the number of members attending the conference.

\(M\) represents the number of members from countries involved in a dispute.

Each of the next t lines contains two integers, \(N\), \(M\), which are separated by a space.

\(N\) represents the number of members attending the conference.

\(M\) represents the number of members from countries involved in a dispute.

Output Format

For each test case output a single integer on a new line, the number of ways in which we can arrange the cars in such a way that no cars of the delegates of countries involved in a dispute are parked adjacent to each other.

Example 1

Input:

1

4 2

Output:

12

Explanation:

Let B1, B2 represent cars of delegates of countries involved in the dispute. Let A1, A2 represent cars of the countries not involved in the dispute. Now, we have to ensure that no two M cars come together.

We can do it in the following ways:

A1 B1 A2 B2

A1 B2 A2 B1

A2 B1 A1 B2

A2 B2 A1 B1

B1 A1 B2 A2

B1 A2 B2 A1

B2 A1 B2 A2

B2 A2 B1 A1

B1 A1 A2 B2

B1 A2 A1 B2

B2 A1 A2 B1

B2 A2 A1 B2

These are the twelve ways to arrange the cars such that no cars of the delegates of countries involved in the dispute are parked next to each other.

Example of incorrect arrangement of cars include:

A1 A2 B1 B2

B2 B1 A2 A1

1

4 2

Output:

12

Explanation:

Let B1, B2 represent cars of delegates of countries involved in the dispute. Let A1, A2 represent cars of the countries not involved in the dispute. Now, we have to ensure that no two M cars come together.

We can do it in the following ways:

A1 B1 A2 B2

A1 B2 A2 B1

A2 B1 A1 B2

A2 B2 A1 B1

B1 A1 B2 A2

B1 A2 B2 A1

B2 A1 B2 A2

B2 A2 B1 A1

B1 A1 A2 B2

B1 A2 A1 B2

B2 A1 A2 B1

B2 A2 A1 B2

These are the twelve ways to arrange the cars such that no cars of the delegates of countries involved in the dispute are parked next to each other.

Example of incorrect arrangement of cars include:

A1 A2 B1 B2

B2 B1 A2 A1