CF1085G Beautiful Matrix

题目描述

Petya在收集美丽矩阵 一个n×n的美丽矩阵要保证: 1.所有的矩阵内的元素都是1~n的整数; 2.每一行不能有相同的元素; 3.每一对竖直相邻的元素不能相同。 Petya定义 稀有度 为将所有n×n的美丽矩阵按照字典序排好序(从0开始计数)该美丽矩阵所在的编号。 他希望你求出他所给的矩阵的稀有度(模 998244353 ) 如 2×2 的美丽矩阵有 1 2 ||| 2 1 2 1 ||| 1 2 0号 ||| 1号 所以样例一中的矩阵的稀有度为1。

输入格式

输出格式

说明/提示

There are only $ 2 $ beautiful matrices of size $ 2 \times 2 $ : ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1085G/f867c5eaa161b1f1aa9e5f2c90e4500d9ce0b908.png)There are the first $ 5 $ beautiful matrices of size $ 3 \times 3 $ in lexicographical order: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1085G/1658b23d01963b8d7e8ba033e0ef04c32e0bd4a6.png)