题目背景

哦咦咦啊咦哦咦咦咦啊咦

STY：你是人我吃。\(\color{white}浅色模式彩蛋\)

题目描述

给定一个 \(n\times n\) 的棋盘，其中 E 代表有敌方棋子，D 代表空位。现在你要摆放 \(k\) 个士，需遵循以下几点：

1.不能摆在敌方棋子上。

2.不能有士可以互相攻击。

请问摆法总数模 \(998244353\) 的余数是多少

位于 \((x,y)\) 的士可以对 \((x\pm1,y\pm1)\) 和 \((x\pm1,y\mp1)\) 4 个位置的士进行黑手。

输入格式

第一行两个整数 \(n\)，\(k\)。

第 2 到第 \(n+1\) 行，每行一个长度为 \(n\) 的字符串，表示棋盘状态。

输出格式

输出一个整数表示答案。

输入输出样例 #1

输入 #1

3 3
EDE
DDD
EDE

输出 #1

2

说明/提示

PS：此题为状压dp，现在还没学，不会别硬做！

对于 \(30\%\) 的数据，\(1\le n \le 4\)。

对于 \(100\%\) 的数据，\(1\le n \le 9\)，\(1\le k\le n\times n\)，表示棋盘状态的字符串只由 E 和 D 构成。