思路

从左到右构造已经打开的结构。设当前处理了 $i$ 台电脑，并形成了 $j$ 个由手动开启顺序连接出的活跃部分。加入下一台电脑时，它可以接到某个部分的左端或右端，共有 $2j$ 种选择；也可以隔开一个将来自动开启的位置，新建一个部分。

做法

令 $f_{i,j}$ 表示已经安排到前 $i$ 个位置、当前有 $j$ 个活跃部分的方案数。初始 $f_{1,1}=1$。

从状态 $(i,j)$ 有两类转移：

• 把下一台电脑接到已有部分的一端，转移到 $(i+1,j)$，方案乘以 $2j$；
• 留出一个会自动开启的位置，并开始新的部分，转移到 $(i+2,j+1)$，新部分可插入 $j+1$ 个相对位置。

所有下标超过 $n$ 的状态忽略。答案为 $\sum_j f_{n,j}$。每次加法和乘法都对 $M$ 取模。

正确性证明

任意合法手动开启序列在从左到右观察时，新增手动开启位置要么与某个已有活跃部分相邻，要么与已有结构之间恰好隔着一个最终自动开启的位置。第一种情况唯一对应选择某个部分的左端或右端；第二种情况唯一对应在部分序列中插入一个新部分。

两类转移互斥且覆盖全部可能，并保留了活跃部分数量。反向删除最右侧构造也能唯一确定来自哪类转移，因此没有重复计数。归纳可知 $f_{i,j}$ 精确统计对应状态，求和即为全部合法方案。

复杂度

状态数为 $O(n^2)$，每个状态常数转移，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。