题目背景

城市规划师林澈接到一项特殊的道路设计任务。全国共有 $n$ 座城市，编号为 $1$ 到 $n$，其中部分城市之间已经修建了双向道路。林澈需要在尚未修建道路的城市对之间，选择若干对修建新的双向道路，使得修路完成后满足一个严格的交通指标：任意两座不同城市之间，简单路径的数量不超过 $2$ 条。他需要知道有多少种不同的修路方案满足这一条件。由于方案数可能很大，请对 $1234567891$ 取模。

题目描述

给定 $n$ 座城市以及它们之间已有的道路，请计算有多少种添加双向道路的方案，使得：

• 添加道路后，任意两座不同的城市 $u, v$（$1 \le u < v \le n$）之间的简单路径数量为 $1$ 或 $2$。

简单路径是指不经过重复顶点的路径。添加方案是指从所有尚未修建道路的城市对中选择一个子集，两座城市之间最多修建一条道路，且不能拆除已有道路。

两种方案不同当且仅当它们添加的道路集合不同。

输入格式

第一行包含一个整数 $n$，表示城市数量。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串，第 $i$ 行第 $j$ 个字符表示城市 $i$ 与城市 $j$ 之间是否已有道路：字符 Y 表示已有道路，字符 N 表示没有道路。

输入保证矩阵是对称的，且对角线字符均为 N。

输出格式

输出一行一个整数，表示满足条件的方案数对 $1234567891$ 取模的结果。

样例

样例输入 1

2
NN
NN

样例输出 1

1

样例解释 1

$2$ 座城市之间没有道路。唯一合法的方案是添加 $(1, 2)$ 之间的道路，形成一棵 $2$ 个顶点的树。添加后任意两个城市之间恰好有 $1$ 条简单路径，满足条件。

样例输入 2

3
NNY
NNN
YNN

样例输出 2

3

样例解释 2

城市 $1$ 和城市 $3$ 之间已有道路。还需要添加边使得图连通且简单路径数 $\le 2$。合法方案有 $3$ 种：添加边 $(1,2)$；添加边 $(2,3)$；同时添加边 $(1,2)$ 和 $(2,3)$ 形成三角形（恰有 $2$ 条简单路径）。

样例输入 3

4
NYNN
YNNN
NNNY
NNYN

样例输出 3

10

样例解释 3

已有两条边 $(1,2)$ 和 $(3,4)$，形成两个树分量。添加边使图成为连通的双重图的方法有 $10$ 种。

数据范围与约定

对于所有测试数据：

• $1 \le n \le 20$；
• 输入矩阵为对称矩阵，对角线元素均为 N；
• 输入描述的城市道路网络是合法的（无重边、无自环）；
• 答案对 $1234567891$ 取模。