Mr. Ham 对字符串，特别是回文串很感兴趣。今天，他找到了一个长度为 $n$ 的字符串 $s$。

对于长度为 $n$ 的字符串 $s$，他定义其从第 $i$ 个字符到第 $j$ 个字符（$1 \le i, j \le n$）的循环子串如下：

• 如果 $i \le j$，循环子串即为 $s$ 从第 $i$ 个字符到第 $j$ 个字符的子串。他将其记作 $s[i..j]$。
• 如果 $i > j$，循环子串即为 $s[i..n] + s[1..j]$，其中 $+$ 表示两个字符串的拼接。他也将其记作 $s[i..j]$。

例如，如果 $s = 12345$，则 $s[2..4] = 234$，$s[4..2] = 4512$，且 $s[3..3] = 3$。

如果一个字符串 $t$ 满足对于所有 $1 \le i \le n$ 都有 $t[i] = t[n - i + 1]$，则称其为回文串。例如，1221 是回文串，而 123 不是。

给定字符串 $s$，其中会有许多循环子串是回文串。记 $P$ 为 $s$ 的所有本质不同的回文循环子串构成的集合，$f(t) (t \in P)$ 为 $t$ 作为循环子串在 $s$ 中出现的次数，$g(t) (t \in P)$ 为 $t$ 的长度。Mr. Ham 希望你计算：

$$\sum_{t \in P} f(t)^2 \times g(t)$$

答案可能非常大，你只需要输出答案对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3 \times 10^6$)，表示字符串 $s$ 的长度。 第二行包含一个长度为 $n$ 的字符串 $s$。$s$ 的每个字符都是数字。

输出格式

输出一个整数，表示求和结果对 $998\,244\,353$ 取模后的值。

样例

样例输入 1

5
01010

样例输出 1

39

样例输入 2

8
66776677

样例输出 2

192

说明

在样例 1 中，$s$ 的回文循环子串有：

• $s[1..1] = s[3..3] = s[5..5] = 0$。
• $s[2..2] = s[4..4] = 1$。
• $s[5..1] = 00$。
• $s[1..3] = s[3..5] = 010$。
• $s[2..4] = 101$。
• $s[4..2] = 1001$。
• $s[1..5] = 01010$。

答案为 $3^2 \times 1 + 2^2 \times 1 + 1^2 \times 2 + 2^2 \times 3 + 1^2 \times 3 + 1^2 \times 4 + 1^2 \times 5 = 39$。