23988번 - Let Me Count The Ways 서브태스크다국어

To celebrate the anniversary of Googleland, N couples are going to go for a boat ride in a rowboat. The rowboat is very long, but it is only one person wide, so the people will sit in a line from front to back.

However, during a rehearsal of the voyage, the boat did not move! After investigating, the organizers found that some newlywed couples were not rowing, but writing love poems for each other the whole time. Specifically, there are M pairs of newlywed couples. If the two members of a newlywed couple are sitting next to each other, they will be so busy writing poems that they will not row.

Now the organizers have come to you, the smartest person in Googleland, to ask, how many possible ways are there to arrange all 2N people on the rowboat, such that for each of the M newlywed couples, the two members are not sitting next to each other? Two ways are different if there is some position in the boat at which the two ways use different people. Notice that for the purpose of counting the number of ways, the two members of a couple are not considered to be interchangeable. Since the number can be very large, the organizers only want to know the value of the answer modulo 1000000007(10⁹+7).

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with two integers N and M as described above.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of possible arrangements, modulo 1000000007(10⁹+7).

• 1 ≤ T ≤ 100.

• 1 ≤ M ≤ N ≤ 100.

• 1 ≤ M ≤ N ≤ 100000.