题目描述

江桥准备去旅游。他搜集了 $n$ 个城市的信息，以及这些城市两两之间不同的有向道路数目，他想制定一个环形旅游路线：

即按照 $k_1,k_2,...,k_x,k_1$ （相邻两个点之前均有有向道路）的计划旅游。

环形路线可以不经过所有城市，但是必须经过至少两个城市，同时环上不能有两个相同的城市。

注意，$4 - 1 - 2 - 3 - 4$ 的环形路线和 $1 - 2 - 3 - 4 - 1$ 是一样的，因为江桥并不关心从哪里开始，如图所示：

和

是同一种方案。

江桥想知道，有多少个这样的环形旅游路线。由于答案很大，你只需要输出答案对 $998244353$ 取模后的值。

输入格式

第一行一个正整数 $n$ 表示城市个数。

接下来 $n$ 行每行 $n$ 个非负整数，第 $i$ 行第 $j$ 个数 $a_{i,j}$ 表示 $i$ 号城市到 $j$ 号城市的不同的单向道路数目。

输出格式

一行一个整数，表示不同的环形旅游路线数量对 $998244353$ 取模后的值。

3
0 1 2
1 0 1
0 1 0

4

样例解释

$4$ 种方案分别为 $1 - 2 - 1,2 - 3 - 2,1 - 3 - 2 - 1(此处的1-3是第一条),1 - 3 - 2 - 1(此处的1-3是第二条)$。

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $2 \leq n \leq 20,0 \leq a_{i,j} \leq 10^{18},a_{i,i} = 0$。