---

Problem 553

---

Power sets of power sets

Let P(n) be the set of the first n positive integers {1, 2, …, n}.
Let Q(n) be the set of all the non-empty subsets of P(n).
Let R(n) be the set of all the non-empty subsets of Q(n).

An element X $\in$ R(n) is a non-empty subset of Q(n), so it is itself a set.
From X we can construct a graph as follows:

• Each element Y $\in$ X corresponds to a vertex and labeled with Y;
• Two vertices Y₁ and Y₂ are connected if Y₁$\cap$Y₂$\neq \emptyset$.

For example, X={ {1},{1,2,3},{3},{5,6},{6,7} } results in the following graph:

This graph has two connected components.

Let C(n,k) be the number of elements of R(n) that have exactly k connected components in their graph.
You are given C(2,1)=6, C(3,1)=111, C(4,2)=486, C(100,10) mod 1000000007 = 728209718.

Find C(10⁴,10) mod 1000000007.

---

幂集的幂集

记P(n)为前n个正整数的集合{1, 2, …, n}。
记Q(n)为P(n)所有非空子集构成的集合。
记R(n)为Q(n)所有非空子集构成的集合。

元素X$\in$R(n)是Q(n)的一个非空子集，因此也是一个集合。
由X我们可以作出如下的一张图：

• 为每个元素Y$\in$X作一个顶点并标记为Y；
• 如果Y₁$\cap$Y₂$\neq \emptyset$则连接顶点Y₁和Y₂。

例如，由集合X={ {1},{1,2,3},{3},{5,6},{6,7} }能作出如下一张图：

这张图有两个连通分量。

记C(n,k)为R(n)中能绘制出恰好k个连通分量的元素的数目。
已知C(2,1)=6，C(3,1)=111，C(4,2)=486，C(100,10) mod 1000000007 = 728209718。

求C(10⁴,10) mod 1000000007。

---