405720: GYM102055 G Pastoral Life in Stardew Valley

Mr. Panda and Mrs. Panda is bored of the hustle and bustle of city life. They decide to make a change. They drop everything they belong to and move to a place where they can find real connections with people and nature. Here in Stardew Valley, they start their life as farmers. They are now embarking on tasks of reclaiming wastelands, sowing seeds, and planting trees.

They are now looking for a rectangle area from the reclaimed wasteland to cultivate their first crop. To prevent crops being damaged by annoying crows, they place several scarecrows inside this rectangle area. The scarecrows occupy a rectangle area that is surrounded by the crops. The wasteland is of $$$N$$$ rows and $$$M$$$ columns. They wonder how many different ways to pick a rectangle area and place crops and scarecrows inside the rectangle. As the number can be large, return the answer modulo $$$10^9+7$$$.

The first line of input gives the number of test cases $$$T$$$($$$1 \leq T \leq 10^5$$$). $$$T$$$ test cases follow. Each test case starts with a line consisting of two integers $$$N$$$, $$$M$$$ ($$$1 \leq N, M \leq 10^5$$$), the number of rows and columns of the wasteland.

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 to place the crops and scarecrows, modulo $$$10^9+7$$$.

3
2 3
3 3
4 4

Case 1: 0
Case 2: 1
Case 3: 25

For test case 1, the wasteland is too small to place any scarecrows.

For test case 2, $$$3\times 3$$$ is the minimal rectangle to place one scarecrow surrounded by 8 crops.

For test case 3, a $$$4\times4$$$ rectangle has 9 ways to place crops and scarecrows: 4 ways for $$$1\times1$$$ scarecrow, 2 ways for $$$1\times2$$$ scarecrows, 2 ways for $$$2\times1$$$ scarecrows, and 1 way for $$$2\times2$$$ scarecrows. Similarly, two $$$3\times4$$$ rectangles has $$$2\times3=6$$$ ways; two $$$4\times3$$$ rectangles has $$$2\times3=6$$$ ways, four $$$3\times3$$$ rectangles has $$$4\times1=4$$$ ways. In total, $$$9+6+6+4=25$$$ ways.