T463910 二进制序列

二进制序列是指仅包含 $0$ 或 $1$ 的序列。 假设 $A$ 是一个二进制序列，定义函数 $f(A)$ 表示 $A$ 的最长不下降子序列的长度。例如，$f(010101)=4$、$f(00)=2$、$f(10)=1$。 现在，输入一个正整数 $n$，然后随机生成一个长度**恰好**为 $n$ 的二进制序列 $A$。你需要计算 $f(A)$ 的期望值。可以证明答案可以写成一个最简分数 $p/q$ 的形式，你需要输出这个分数对素数 $M$ 取模之后的结果，即输出 $(p \cdot q^{-1}) \bmod M$，其中 $q^{-1}$ 表示 $q$ 在 $M$ 下的逆元。

无

无

**【样例解释 \#2】** 对于 $n=2$，随机生成的序列的所有可能为：```00 01 10 11```，其对应的函数值分别为 $2, 2, 1, 2$，所以答案为 $\frac{1}{4} (2 + 2 + 1 + 2) = \frac{7}{4}$。 --- **【数据范围】** 对于 30% 的数据，$n \le 10$。 对于 60% 的数据，$n \le 200$。 对于 90% 的数据，$n \le 5000$。 对于 100% 的数据，$1 \le n \le 10^6$，$10^8 \le M \le 10^9$，$M$ 是素数。