String Circle
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

给定 k 个长度均为 n 的字符串 s_0,s_1,\cdots,s_{k-1}。

请计算有多少种不同的长度为 k 的字符串序列 [t_0,t_1,\cdots,t_{k-1}]，使得：

  • s_0=t_0+t_1+\cdots+t_{k-2}+t_{k-1}；
  • s_1=t_1+t_2+\cdots+t_{k-1}+t_0；
  • \cdots
  • s_i=t_i+t_{i+1}+\cdots+t_{k-1}+t_0+t_1+\cdots+t_{i-1}；
  • \cdots
  • s_{k-1}=t_{k-1}+t_0+\cdots+t_{k-3}+t_{k-2}。

对 998244353 取模。注意 [t_0,t_1,\cdots,t_{k-1}] 中可以存在空串。

其中，s+t 表示字符串 s 和字符串 t 顺次拼接。

2\leq n,k,n\cdot k\leq 5\times 10^6。

输入描述:

第一行两个整数 n,k，分别表示字符串的长度和个数。

接下来 k 行每行一个长度为 n，仅包含小写字母的字符串，依次分别为 s_0,s_1,\cdots,s_{k-1}。

输出描述:

一行一个整数表示答案。
示例1

输入

复制 
3 3
abc
bca
cab

输出

复制 
1
示例2

输入

复制 
3 3
aaa
aaa
aaa

输出

复制 
10