Problem Description

Given a string \( S \) consisting only of lowercase letters, determine how many strings of length \( n \) consisting only of lowercase letters contain \( S \) exactly twice. The answer should be taken modulo \( 998,244,353 \).

Input Format

A single line containing a string \( S \) and an integer \( n \), separated by a space.

Output Format

A single line containing an integer representing the answer.

Sample Input and Output

Sample Input #1

aba 6

Sample Output #1

53

Sample Input #2

aba 10

Sample Output #2

77907666

Notes

For 40% of the test cases, \( n \leq 20 \) and \( |S| \leq 6 \);
For another 10% of the test cases, \( n \leq 500 \) and \( |S| \leq 2 \);
For 70% of the test cases, \( n \leq 10^5 \);
For all test cases, \( 1 \leq n \leq 10^9 \) and \( 1 \leq |S| \leq 30 \).

见题面 Input 部分

见题面 Output 部分