U534157 矩阵革命（matrix）（T4）

$\qquad\!\!$LHRG李 最近看了一部早些年的科幻大片：《黑客帝国》。 $\qquad\!\!$一名年轻的网络黑客尼奥发现看似正常的现实世界实际上是由一个名为“矩阵”的计算机人工智能系统控制的，尼奥在一名神秘女郎崔妮蒂的引导下见到了黑客组织的首领墨菲斯，三人走上了抗争矩阵的征途。

$\qquad\!\!$要想与矩阵作对，就要让矩阵中的人觉醒。“矩阵”虽然连接着所有人的意识，但实际上它就是一个实实在在的 $01$矩阵。用 $f$ 表示矩阵，则 $f_{i,j}=1$ 代表编号为 $i$ 的人与编号为 $j$ 的人有从 $i$ 到 $j$ 的意识连接，$f_{i,j}=0$ 则代表没有。（并没有规定 $i\not= j$） $\qquad\!\!$假设矩阵中有 $n$ 个人类，每个人的意识可以通过其他人进行传输。即对于编号为 $a$ 的人与编号为 $b$ 的人有从 $a$ 到 $b$ 的意识连接，且编号为 $b$ 的人与编号为 $c$ 的人有从 $b$ 到 $c$ 的意识连接,那么编号为 $a$ 的人与编号为 $c$ 的人就有从 $a$ 到 $c$ 的意识连接。已知矩阵 $f$ 中每个数 $f_{i,j}$ 为 $1$ 和 $0$ 的概率相同。那么，请你求出这 $n$ 个人中任意两人彼此之间都有从对方到自己和从自己到对方的意识连接的概率为多少？ $\qquad\!\!$由于答案可能为分数，请输出它对于 $19999999$ 取模的得数。

一个正整数，$n$。

一个正整数，表示取模后的得数。

数据范围： | 子任务 | 测试点编号 | 总分数 | 数据范围 | | :----: | :----: | :----: | :----: | | **Subtask #1** | $1-4$ | 8 | $1\leqslant n \leqslant 5$ | | **Subtask #2** | $5-12$ | 16 | $1\leqslant n \leqslant 50$ | | **Subtask #3** | $13-20$ | 16 | $1\leqslant n \leqslant 500$ | | **Subtask #4** | $21-40$ | 60 | $1\leqslant n \leqslant 2400$ | 对于 $100\%$ 的数据：$1\leqslant n \leqslant 2400$ 样例一解释： 一共有 $16$ 种相等概率的情况： $00\ \ 00\ \ 00\ \ 00\ \ 01\ \ 01\ \ 01\ \ 01\\00\ \ 01\ \ 10\ \ 11\ \ 00\ \ 01\ \ 10\ \ 11\\\ \ \\ 10\ \ 10\ \ 10\ \ 10\ \ 11\ \ 11\ \ 11\ \ 11\\ 00\ \ 01\ \ 10\ \ 11\ \ 00\ \ 01\ \ 10\ \ 11$ 其中只有 $7,8,15,16$ 符合题意，则答案为 $\dfrac{1}{4}\mod 19999999 =5000000$。 [题解](http://lhrg.github.io/题解-U534157-【矩阵革命】/) ------------ 出题者：LHRG李