Problem Description

Given a string $S$ consisting only of lowercase letters, ask how many strings of length $n$ consisting only of lowercase letters contain $S$ exactly twice. Output the answer modulo $998\ 244\ 353$.

Input Format

Input one line containing a string $S$ and an integer $n$, separated by a space.

Output Format

Output one line containing one integer representing the answer.

aba 6

53

aba 10

77907666

Hint

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

Translated by ChatGPT 5