Counting Strings with Exactly Two Occurrences

You are given a string \( S \) consisting only of lowercase letters and an integer \( n \). Your task is to count the number of strings of length \( n \) (also consisting only of lowercase letters) in which the string \( S \) appears exactly twice as a substring. Two occurrences may overlap. Output your answer modulo \( 998244353 \).

Note: When an occurrence of \( S \) is completed, the matching state is reset according to the longest proper prefix which is also a suffix of \( S \) (i.e. using the \( \pi \) function from KMP algorithm).

inputFormat

The input consists of two lines. The first line contains the string \( S \) consisting only of lowercase letters. The second line contains an integer \( n \), the length of the strings to be considered.

outputFormat

Output a single integer: the number of strings of length \( n \) in which \( S \) appears exactly twice, modulo \( 998244353 \).

sample

a
2

1