OI 出题 - 士

题目背景

哦咦咦啊咦哦咦咦咦啊咦

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

题目描述

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

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

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

请问摆法总数模 \(998244353\cdot\frac{6\cdot\sum^\infty_{n=1}\frac{1}{n^2}}{\pi^2}\) 的余数是多少（看注释）。^[1]

位于 \((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

说明/提示

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

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

。

我是彩蛋 $\color{red}彩\color{orange}彩\color{yellow}彩\color{green}彩\color{cyan}彩{blue}彩\color{purple}彩$

---

1. \[\frac{6\cdot\sum^\infty_{n=1}\frac{1}{n^2}}{\pi^2}=1 \]
   ↩︎