Rin's Space Time Game

In space, besides freely creating in her virtual world, Rin plays an interesting game every day. Initially, her father left her a non‐empty string \(s\) consisting of lowercase English letters, with length \(n\). Every day, she finds the largest integer \(i\) (\(0 \le i < |s|\)) such that the prefix of length \(i\) is equal to the suffix of length \(i\) (note that \(i\) may be \(0\)). Then, she appends this prefix (which is also the suffix) to the end of the entire string to form a new string.

For example, if \(s = \texttt{mivikismivik}\), then the maximum \(i\) is \(5\) (since both the prefix and suffix of length \(5\) are \(\texttt{mivik}\)). Hence, Rin appends \(\texttt{mivik}\) to get \(\texttt{mivikismivikmivik}\).

After playing for \(K\) days in space, the string has become very long. Rin is curious about its current length. Your task is to compute the length of the string modulo \(998244353\).

Note on the Process

Let \(L_0 = n\) be the initial length and let \(f(s)\) be the maximum \(i\) (with \(0 \le i < |s|\)) such that the prefix and suffix of \(s\) match. Then the length evolves as:

[ L_{k+1} = L_k + f(s_k), \quad k \ge 0. ]

It turns out that the evolution depends on the structure of the initial string \(s\). Define \(r = f(s)\) computed on the initial string and let \(p = n - r\). There are two cases:

1. If \(r = 0\), no non-empty border exists and the string never grows; thus \(L_K = n\).
2. If \(r \ne 0\} and \(n\) is divisible by \(p\) (i.e. \(n \bmod p = 0\)), then \(s\) is periodic and for any day \(k\) the longest border of \(s_k\) is \(L_k - p\). In this case, the recurrence is
   \(L_{k+1} = 2L_k - p\). Solving it gives:
   \[ L_K = 2^K \cdot n - p \cdot (2^K - 1). \]
3. If \(r \ne 0\) but \(n \bmod p \ne 0\), the longest border remains constant and equal to \(r\) for every day. Hence, in this case,
   \[ L_K = n + K \cdot r. \]

You are to compute \(L_K \bmod 998244353\).

inputFormat

The input consists of two lines. The first line contains the initial string (s) (a non-empty string of lowercase English letters). The second line contains an integer (K) representing the number of days.

outputFormat

Output a single integer: the length of the final string after (K) days, modulo (998244353).

sample

aba
3

6