#P18766. Expected Symmetry

Expected Symmetry

Expected Symmetry

题目描述

给定一个长度为 2n2n 的二进制字符串 s1s2…s2ns_1s_2\ldots s_{2n}。

考虑如下随机过程:

  1. 从 11 到 nn 中等概率地选择一个整数 kk。
  2. 考察前缀 s1s2…s2ks_1s_2\ldots s_{2k}。如果存在一个对称位置 ii(1≤i≤k1\le i\le k),使si=s2k−i+1,s_i=s_{2k-i+1}, 则过程立刻结束。
  3. 否则,对于每个 1≤i≤2k1\le i\le2k,分别独立地以 1/21/2 的概率翻转 sis_i 的值。之后重新执行上述步骤,选择下一个 kk。

不同步骤中选择的 kk 相互独立。所有位是否翻转的事件,在不同位置以及不同步骤之间也都相互独立。

请计算该过程结束时经历的步数期望,包括过程结束的那一步。可以证明答案可以表示为最简分数 p/qp/q,请输出

p⋅q−1(mod998244353).p\cdot q^{-1}\pmod{998244353}.

注意:停止条件是存在至少一对镜像位置上的值相同,并不要求整个前缀是回文。

输入格式

第一行包含一个整数 nn。

第二行包含长度为 2n2n 的二进制字符串 s1s2…s2ns_1s_2\ldots s_{2n}。

数据范围

  • n∈{10,107}n\in\{10,10^7\};
  • 字符串只包含字符0和1,长度恰好为 2n2n。

输出格式

输出一个整数,表示期望步数对998244353取模后的值。

样例

输入:

10
01010000111101010000

输出:

222017723