题目描述

锦标赛图是一种有向图：任意两个不同顶点之间恰好存在一条有向边。

给定一个包含 $b$ 个顶点的锦标赛图 $G$，顶点编号为 $0,1,\ldots,b-1$。邻接矩阵 graph 中，graph[i][j]='Y' 表示存在边 $i\to j$，否则为 'N'。

再给定整数 $k$。构造一个包含 $b^k$ 个顶点的大锦标赛图，顶点编号为 $0,1,\ldots,b^k-1$。把任意顶点编号写成恰好 $k$ 位的 $b$ 进制数，不足的在左侧补零。

对于两个不同顶点 $x,y$，找到它们从左到右第一个不同的数位。设该位置上的数字分别为 $p,q$，则大图中 $x$ 与 $y$ 之间边的方向与基础图 $G$ 中 $p$ 与 $q$ 之间边的方向相同。

一个非空有向图称为强连通，当且仅当任意两个顶点之间都存在有向路径。单个顶点也视为强连通。

求这个大锦标赛图中有多少个非空顶点子集，其诱导子图是强连通的。答案对 $998244353$ 取模。

输入格式

第一行两个整数 $b,k$。

接下来 $b$ 行，每行一个长度为 $b$ 的字符串，表示基础锦标赛图的邻接矩阵。

输出格式

输出强连通非空诱导子图的数量，对 $998244353$ 取模。

数据范围

• $3\le b\le23$；
• $1\le k\le1000$；
• 输入矩阵保证描述一个合法锦标赛图。

样例 1

3 2
NYN
NNY
YNN

355

样例 2

3 2
NYY
NNY
NNN

9