题目背景

It's a long way forward, so trust in me

I'll give them shelter, like you've done for me

And I know, I'm not alone

You'll be watching over us, until you're gone

题目描述

在太空里的时间，Rin 除了在虚拟世界里自由创作，每天还会进行一个有趣的小游戏。

最初来到太空时，她的父亲留给她了一个由英文小写字母组成的非空的字符串 $s$，其长度为 $n$。每天，Rin 都会找到一个最大的整数 $i$（$0\le i<|s|$）使得字符串的长度为 $i$ 的前缀与其长度为 $i$ 的后缀相同（注意 $i$ 可能为 $0$），并将这个 前缀 / 后缀 追加在整个字符串的最后面形成新的字符串。例如，当字符串为 mivikismivik 时，最大的 $i=5$（字符串长为 $5$ 的前缀后缀皆为 mivik），于是 Rin 将 mivik 追加在字符串后面形成新字符串 mivikismivikmivik。

在太空中度过 $K$ 天后，这个字符串已经变得很长，Rin 突然很好奇这个字符串的长度现在是多少，你能帮帮她吗？由于答案可能很大，你只需要告诉她答案对 $998244353$ 取模的结果即可。

输入格式

第一行两个正整数 $n,K$，分别代表最初字符串的长度和 Rin 在太空中度过的天数。

第二行一个长度为 $n$ 的小写英文字母组成的字符串 $s$，代表 Rin 的父亲留给她的字符串。

输出格式

一行一个整数，代表 $K$ 天后字符串的长度对 $998244353$ 取模的结果。

7 1
abcdabc

10

5 2
ioioi

11

8 50
idolidol

263923940

提示

样例解释

样例一：操作一次后得到字符串 abcdabcabc，长度为 $10$。

样例二：操作一次后得到字符串 ioioiioi，再操作一次得到 ioioiioiioi，长度为 $11$。

数据范围

对于全部数据，有 $1\le n\le 2\cdot 10^6$，$1\le K\le 10^{18}$。

Subtask 1 (15 pts)：保证 $s$ 只由一种字母构成。

Subtask 2 (20 pts)：保证 $s$ 有长度不为 $|s|$ 的整周期（即长度是 $|s|$ 的约数的周期）。

Subtask 3 (65 pts)：无特殊限制。