Problem: patrols (2017 finals)

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



Sample input:
5
2 2 2
3 3 3
10 10 2
10 10 3
12345 54321 98765


Sample output:
Case #1: 10
Case #2: 411
Case #3: 1046530
Case #4: 367947134
Case #5: 151251795



Code: // Hacker Cup 2017
// Final Round
// Fox Patrols
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define MOD 1000000007

// a^b
int pw(LL a,int b)
{
	int v=1;
		while (b)
		{
				if (b&1)
					v=v*a%MOD;
			a=a*a%MOD;
			b>>=1;
		}
	return(v);
}

// number of skylines of length n with max height h
LL cnt(int n,int h)
{
	return((pw(h,n)-pw(h-1,n)+MOD)%MOD);
}

int main()
{
	// vars
	int T,t;
	int N,M,H;
	int h,ans;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N),Read(M),Read(H);
			// consider all possible max tree heights
			ans=0;
				Fox1(h,H)
					ans=(ans+cnt(N,h)*cnt(M,h))%MOD;
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}