To celebrate the anniversary of Googleland, 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 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 people on the rowboat, such that for each of the 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 .
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case consists of one line with two integers and as described above.
输出格式
For each test case, output one line containing Case #x: y, where x is the test case number (starting from ) and y is the number of possible arrangements, modulo .
样例
样例输入 1
5
2 1
2 2
3 1
3 2
10 5
样例输出 1
Case #1: 12
Case #2: 8
Case #3: 480
Case #4: 336
Case #5: 560963525
数据范围与提示
In Sample Case #1, there are 2 couples. To make the description simpler, we use the characters A and a to represent the newlywed couple, and B and b to represent the other couple. Per the rules of the problem, A and a cannot be adjacent. There are 12 ways to arrange the four people:
ABab ABba AbaB AbBa
aBAb aBbA abAB abBA
BAba BabA bABa baBA
In Sample Case #2, both two couples are newlywed couples, so A and a cannot be adjacent, and B and b cannot be adjacent. They can be arranged in the following 8 ways:
