N. [L3-2] 超级恶臭字符串

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

若两个字符串 完全相同,即 ,且对于任意的 都有 ,则我们记 . 否则,我们记 .

若有两个字符串 ,我们记这两个字符的拼接为 .

若有一个字符串 ,我们记其子串 .

我们称一个字符串 的恶臭程度为 ,表示将 分割 个字符串 ,且这 个字符串满足如下性质的方案数

  • .

  • .

  • .

  • 不能为空串.

对于两个分割 ,只要存在一个 )使得 ,则视为两个不同的分割方案.

例如, 就是一个恶臭程度为 的字符串,因为其可以分割为 ,满足之前所述的条件,并且不存在其他分割方式.

定义一个长度为 的字符串 的超级恶臭程度 ,为 的所有子串的恶臭程度之和. 即:

给定一个字符串 ,求其超级恶臭程度 ,对 998244353 取模的结果.

输入格式

第一行包含一个正整数 ,表示字符串 的长度.

第二行包含一个字符串 . 保证 仅由数字 构成.

输出格式

输出一行,包含一个整数,表示 的超级恶臭程度,对 998244353 取模的结果.

样例

输入样例 1

7
1919810

输出样例 1

1

输入样例 2

11
11011011110

输出样例 2

12

数据范围与提示

保证字符串 仅由数字 构成.