406528: GYM102431 L Spiral Matrix

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Spiral Matrixtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Lee got a ticket to the Google Developer Day. When he came to the exhibition hall, he found that the booths were located in a matrix of size $$$n \times m$$$.

Unfortunately, Lee had badly sprained his left ankle a week before the GDD when playing basketball. As a result, he couldn't wander freely as he wanted. His ankle would get hurt if he tried to turn left. Lee also didn't want to make a big right turn by turning right multiple times, which would make him look stupid.

Lee wanted to visit each booth exactly once. Given his ankle situation, he made some rules visiting the booths. He could start with any booth in the exhibition hall, and choose an initial direction. Then each move would have to follow one of the possible moves:

  1. Go straight to visit the next booth.
  2. Turn right once and then go straight to visit the next booth.

You are a friend of Lee and you have the good habit of helping him. Can you find out the number of different ways to visit each booth exactly once? Two ways are considered different if and only if the visiting orders in these two ways vary.

Input

The first line of the input gives the number of test cases, $$$T$$$ ($$$1 \le T \le 100$$$). $$$T$$$ test cases follow.

For each test case, the first and only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 100$$$), the number of rows and the number of columns of the matrix, respectively.

Output

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 different ways modulo ($$$10^9+7$$$).

ExampleInput
1
2 2
Output
Case #1: 4
Note

Here are the 4 different ways for $$$n = 2, m = 2$$$.

加入题单

上一题 下一题 算法标签: