406051: GYM102222 M Acyclic Orientation

The chromatic polynomial is a graph polynomial. It counts the number of graph colourings as a function of the number of colours.

Precisely speaking, for an undirected graph $$$G$$$, $$$\chi_G(k)$$$ counts the number of its vertex k-colourings. Here a vertex k-colouring of $$$G$$$ is an assignment of one of $$$k$$$ possible colours to each vertex of $$$G$$$ such that no two adjacent vertices receive the same colour. There is a unique polynomial $$$\chi_G(x)$$$ which evaluated at any integer $$$k\ge 0$$$ coincides with $$$\chi_G(k)$$$. If $$$G$$$ has $$$n$$$ vertices, the chromatic polynomial $$$\chi_G(x)$$$ is of degree exactly $$$n$$$ with integer coefficients.

Malak can use the chromatic polynomial to solve several interesting problems, including the question about acyclic orientation. In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph (DAG). Every graph $$$G$$$ has exactly $$$|\chi_G(-1)|$$$ different acyclic orientations, so in this sense, an acyclic orientation can be interpreted as a colouring with $$$-1$$$ colours.

Now Malak shows you a complete bipartite graph with $$$n$$$ and $$$m$$$ vertices in its two sets respectively, denoted by $$$K_{n,m}$$$. You are asked to count the number of different acyclic orientations of $$$K_{n,m}$$$.

The input contains several test cases, and the first line is a positive integer $$$T$$$ indicating the number of test cases which is up to $$$600$$$.

Each test case is described by three integers $$$n, m~(1\le n,m\le 60000)$$$ which are the size of the given complete bipartite graph and $$$q~(10^8 \leq q \leq 10^9)$$$ which is a prime number for the output.

We guarantee that no more than $$$60$$$ test cases satisfy $$$n > 60$$$ or $$$m > 60$$$, and no more than $$$6$$$ test cases satisfy $$$n > 600$$$ or $$$m > 600$$$.

For each test case, output a line containing Case #x: y, where x is the test case number starting from $$$1$$$, and y is the remainder of the number of different acyclic orientations dividing by $$$q$$$.

4
1 1 998244353
1 2 998244353
2 1 998244353
2 2 998244353

Case #1: 2
Case #2: 4
Case #3: 4
Case #4: 14