Counting Palindromic Substrings in a Repeated String

You are given a string \(s\) consisting only of lowercase English letters and an integer \(k\). Construct the string \(t = s^k\) by concatenating \(s\) with itself \(k\) times. Your task is to calculate the total number of palindromic substrings in \(t\). Note that two substrings are considered different if they occur at different positions in \(t\), even if they are equal.

Formally, given \(s\) and \(k\), count the number of substrings in \(t = s^k\) that are palindromes. Since this number can be very large, output it modulo \(998244353\).

A palindrome is a string that reads the same forward and backward.

Input Format:

1. The first line contains the string \(s\) (only lowercase English letters).
2. The second line contains an integer \(k\).

Output Format:

Output a single integer representing the count of palindromic substrings in \(t = s^k\) modulo \(998244353\).

inputFormat

The input consists of two lines:

1. A string \(s\) which contains only lowercase English letters.
2. An integer \(k\) on the next line.

You can assume that \(s\) and \(k\) are such that \(t = s^k\) can be processed by your program within reasonable time constraints.

outputFormat

Output a single integer: the number of palindromic substrings in the string \(t = s^k\), taken modulo \(998244353\).

sample

aba
2

11