A certain well-hidden valley is home to a thriving population of mysterious
creatures — Foxen! However, keeping the valley safe from outsiders (such as
humans) is a necessity. To that end, a group of Foxen have been sent out to
patrol the border.

On their patrol route, the Foxen know that they're going to pass by an
interesting, rectangular forest. When viewed from above, the forest can be
modeled as a grid of cells with **R** rows and **C** columns. The rows are
numbered from 1 to **R** from North to South, while the column are numbered
from 1 to **C** from West to East. One tree is growing in the center of each
cell, and each tree's height (in metres) is some positive integer no larger
than **H**.

If the Foxen were to look at the forest from the North side, all of the trees
in any given column of cells would obscure each other and blend together. In
fact, the Foxen would really only be able make out the overall shape of the
forest's "skyline" when viewed from that direction. This Northern skyline can
be expressed as a sequence of **C** positive integers, with the _i_th one
being the largest of the **R** tree heights in the _i_th column.

Similarly, if they were to look at the forest from the West side, they would
only be able to make out the shape of its skyline from that direction. This
Western skyline is a sequence of **R** positive integers, with the _i_th one
being the largest of the **C** tree heights in the _i_th row.

On their way to the forest, the Foxen find themselves wondering about what it
might look like. They've done their research and are aware of its dimensions
**R** and **C**, as well as the maximum possible height of its trees **H**,
but they don't know the actual heights of any of its trees. They'd like to
determine how many different, distinct-looking forests they might end up
finding. A forest is a set of heights for all **R**x**C** trees, and two
forests are considered to be distinct-looking from one another if their
Northern skyline sequences differ and/or their Western skyline sequences
differ.

Please help the Foxen determine the number of possible different, distinct-
looking forests! As this quantity may be quite large, they're only interested
in its value when taken modulo 1,000,000,007.

### Input

Input begins with an integer **T**, the number of different forests visited by
the Foxen. For each forest, there is a single line containing the three space-
separated integers **R**, **C**, and **H**.

### Output

For the _i_th forest, print a line containing "Case #**i**: " followed by the
number of possible different, distinct-looking forests modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 30
1 ≤ **R**, **C**, **H** ≤ 500,000

### Explanation of Sample

In the first case, there are 10 possible different, distinct-looking forests
which consist of a 2x2 grid of trees, with each tree being either 1m or 2m
tall. For example, the following 2 forests look different (even though their
Western skylines are equal, their Northern skylines differ), so both should be
counted:

1 2 2 1
1 1 1 1

On the other hand, the following 2 forests look identical to one another from
both the North and the West, so only one of them should be counted:

1 2 2 2
2 1 2 1