题目描述

有一个迷宫，迷宫由房间和单向的走廊组成。每条走廊都是从一个房间单向走向另一个房间。房间编号为 $0$ 到 $n$。迷宫有一个性质，对于每个房间，一旦通过走廊离开房间，则无法再回到这个房间。

每个房间可能或者不可能包含一个障碍物。有障碍物的房间则无法通过。

如果有 $k$ 个房间可能包含障碍物，则整个迷宫有 $2^k$ 种状态。问在这些状态中，有多少种状态，从 $0$ 号房间到 $1$ 号房间有偶数条路径。

输入格式

第一行一个整数 $n$。

第二行一个长度为 $n$ 的字符串，第 $i$ 个字符为 - 或 ?。- 表示第 $i-1$ 个房间不含有障碍物，? 表示第 $i-1$ 个房间可能含有障碍物。

第三行至结束是一个邻接矩阵，第 $i$ 行第 $j$ 列为 Y 则表示房间 $i$ 到 $j$ 有一条单向走廊。

输出格式

一个整数，如题目中描述。

5
--???
NYYNN
NNNNY
NYNNN
YNNNN
NNNNN

4

提示

对于 $100\%$ 的数据，$1 \le n \le 50$，邻接矩阵中最多有 $500$ 个 Y，? 最多有 $32$ 个，$0$ 号和 $1$ 号房间不会有可能有障碍物。