DA.DA.S

영어 대문자로만 이루어진 문자열 $S_1,S_2,\ldots,S_N$이 주어진다.

영어 대문자로만 이루어진 문자열 $X$에서 부분 문자열을 몇 개 고르려고 한다. 고른 부분 문자열은 각각 $S_1,S_2,\ldots,S_N$ 중 하나와 같아야 하며, 서로 같은 위치의 문자를 포함해서는 안 된다. 여기서 부분 문자열은 연속한 문자들로 이루어진 문자열이다. 고른 부분 문자열들이 바로 붙어 있는 것은 허용한다.

같은 문자열과 일치하는 부분 문자열을 여러 번 골라도 된다. 주어진 문자열 중 같은 것이 여러 개 있더라도, 같은 위치의 부분 문자열을 여러 번 고를 수는 없다.

이렇게 고를 수 있는 부분 문자열의 최대 개수를 $f(X)$라고 하자. 아무것도 고를 수 없다면 $f(X)=0$이다. 예를 들어, 주어진 문자열이 $\texttt{AA}$ 하나일 때 $f(\texttt{AAAA})=2$이다. 앞의 두 문자와 뒤의 두 문자를 각각 고를 수 있기 때문이다. 반면, 에 있는 두 개의 는 가운데 문자를 공유하므로 이다.

영어 대문자로만 이루어진 길이 $M$의 모든 문자열 $X$에 대한 $f(X)$의 합을 $998\ 244\ 353$으로 나눈 나머지를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 길이 $M$의 모든 영어 대문자 문자열 $X$에 대한 $f(X)$의 합을 $998\ 244\ 353$으로 나눈 나머지를 한 줄에 출력한다. 테스트 케이스가 입력된 순서대로 출력한다.

• $1\leq T\leq 100$.
• $1\leq N\leq 100$.
• $1\leq M\leq 10^{18}$.