Problem 716

Grid Graphs

Consider a directed graph made from an orthogonal lattice of $H \times W$ nodes. The edges are the horizontal and vertical connections between adjacent nodes. $W$ vertical directed lines are drawn and all the edges on these lines inherit that direction. Similarly, $H$ horizontal directed lines are drawn and all the edges on these lines inherit that direction.

Two nodes, $A$ and $B$ in a directed graph, are strongly connected if there is both a path, along the directed edges, from $A$ to $B$ as well as from $B$ to $A$ . Note that every node is strongly connected to itself.

A strongly connected component in a directed graph is a non-empty set $M$ of nodes satisfying the following two properties:

All nodes in $M$ are strongly connected to each other.
$M$ is maximal, in the sense that no node in $M$ is strongly connected to any node outside of $M$ .

There are $2^{H} \times 2^{W}$ ways of drawing the directed lines. Each way gives a directed graph $G$ . We define $S (G)$ to be the number of strongly connected components in $G$ .

The illustration below shows a directed graph with $H = 3$ and $W = 4$ that consists of four different strongly connected components (indicated by the different colours).

Define $C (H, W)$ to be the sum of $S (G)$ for all possible graphs on a grid of $H \times W$ . You are given $C (3, 3) = 408$ , $C (3, 6) = 4696$ and $C (10, 20) \equiv 988971143 (\mod 1 000 000 007)$ .

Find $C (10 000, 20 000)$ giving your answer modulo $1 000 000 007$ .

格阵图

考虑一张基于 $H \times W$ 个结点组成的格阵所构成的有向图，图中的边水平或竖直连接着相邻的结点。在格阵上可以画出 $W$ 条竖直的有向直线，所有落在直线上的边和相应直线的方向一致；同理，在格阵上可以画出 $H$ 条水平的有向直线，所有落在直线上的边和相应直线的方向也一致。

在有向图中，如果在两个结点 $A$ 和 $B$ 之间，存在一条沿着有向边由 $A$ 到 $B$ 的路径，同时也存在一条沿着有向边由 $B$ 到 $A$ 的路径，则称这两个结点是强连通的。注意每个结点和其自身都是强连通的。

有向图中的一个强连通分支是指满足以下两条性质的非空结点集 $M$ ：

$M$ 中的任意两个结点之间都是强连通的。
$M$ 是极大的，这意味着不存在 $M$ 之内的结点和 $M$ 之外的结点之间是

共有 $2^{H} \times 2^{W}$ 种绘制有向直线的方式，每种方式确定了一张有向图 $G$ 。记 $S (G)$ 为 $G$ 中强连通分支的数目。

下图展示了 $H = 3$ 、 $W = 4$ 时的一张有向图，这张图有四个不同的强连通分支（用不同颜色表示）。

记 $C (H, W)$ 为所有基于 $H \times W$ 的格阵的有向图对应 $S (G)$ 之和。已知 $C (3, 3) = 408$ ， $C (3, 6) = 4696$ ， $C (10, 20) \equiv 988971143 (\mod 1 000 000 007)$ 。

求 $C (10 000, 20 000)$ 并将你的答案对 $1 000 000 007$ 取余。