Problem 690

Tom and Jerry

Tom (the cat) and Jerry (the mouse) are playing on a simple graph $G$ .

Every vertex of $G$ is a mousehole, and every edge of $G$ is a tunnel connecting two mouseholes.

Originally, Jerry is hiding in one of the mouseholes.
Every morning, Tom can check one (and only one) of the mouseholes. If Jerry happens to be hiding there then Tom catches Jerry and the game is over.
Every evening, if the game continues, Jerry moves to a mousehole which is adjacent (i.e. connected by a tunnel, if there is one available) to his current hiding place. The next morning Tom checks again and the game continues like this.

Let us call a graph $G$ a Tom graph, if our super-smart Tom, who knows the configuration of the graph but does not know the location of Jerry, can guarantee to catch Jerry in finitely many days. For example consider all graphs on $3$ nodes:

For graphs $1$ and $2$ , Tom will catch Jerry in at most three days. For graph $3$ Tom can check the middle connection on two consecutive days and hence guarantee to catch Jerry in at most two days. These three graphs are therefore Tom Graphs. However, graph $4$ is not a Tom Graph because the game could potentially continue forever.

Let $T (n)$ be the number of different Tom graphs with $n$ vertices. Two graphs are considered the same if there is a bijection $f$ between their vertices, such that $(v, w)$ is an edge if and only if $(f (v), f (w))$ is an edge.

We have $T (3) = 3$ , $T (7) = 37$ , $T (10) = 328$ and $T (20) = 1416269$ .

Find $T (2019)$ giving your answer modulo $1 000 000 007$ .

猫和老鼠

汤姆（猫）和杰瑞（老鼠）在玩游戏，他们玩游戏的地图可以用简单图 $G$ 表示。

$G$ 中的每一个顶点代表一个老鼠洞，而 $G$ 中的每一条边代表连通两个老鼠洞的一条地道。

一开始，杰瑞躲在其中一个老鼠洞中。
每天早上，汤姆可以查看一个老鼠洞。如果杰瑞恰好躲在这个老鼠洞中，那么汤姆抓住杰瑞，游戏结束。
每天晚上，如果游戏没有结束，杰瑞会从当前藏身的老鼠洞移动到一个相邻（有地道直接相连）的老鼠洞。第二天早上再次轮到汤姆查看一个老鼠洞，依此类推。

汤姆不知道杰瑞的位置，但他知道图 $G$ 的形状，如果超级聪明的汤姆能保证在有限天内抓住杰瑞，那么我们称图 $G$ 为汤姆图。考虑如下有 $3$ 个顶点的图：

对于图 $1$ 和 $2$ ，汤姆可以在至多三天内抓住杰瑞。对于图 $3$ ，汤姆只需连续两天都检查右下角的老鼠洞，就能保证在至多两天内抓住杰瑞。因此这三张图都是汤姆图。然而，图 $4$ 不是汤姆图，因为这个游戏有可能永远不会结束。

记 $T (n)$ 为有 $n$ 个顶点的不同汤姆图的数量。如果两张图的顶点间存在双射 $f$ ，使得 $(v, w)$ 是第一张图的一条边当且仅当 $(f (v), f (w))$ 是第二张图的一条边，这两张图就被认为是相同的图。

已知 $T (3) = 3$ ， $T (7) = 37$ ， $T (10) = 328$ ， $T (20) = 1416269$ 。

求 $T (2019)$ 并将你的答案对 $1 000 000 007$ 取余。