有一个迷宫,迷宫由房间和单向的走廊组成.每条走廊都是从一个房间单向走向另一个房间.房间编号为0到N-1.迷宫有一个性质,对于每个房间,一旦通过走廊离开房间,则无法再回到这个房间.
每个房间可能或者不可能包含一个障碍物.有障碍物的房间则无法通过.
如果有K个房间可能包含障碍物,则整个迷宫有2^K种状态.问在这些状态中,有多少种状态,从0号房间到1号房间有偶数条路径.
第二行一个长度为N的字符串,第i个字符为-或?.-表示第i-1个房间不含有障碍物,?表示第i-1个房间可能含有障碍物.
第三行至结束是一个邻接矩阵,第i行第j列为Y则表示房间i到j有一条单向走廊.
对于100%的数据,1<=N<=50,邻接矩阵中最多有500个Y,?最多有32个,0号和1号房间不会有可能有障碍物.