#P1027. 卷王
卷王
题目描述
卷王所在的地方可以看做一个 的正方形区域,每个位置 上都有一个摆烂人。
卷王实在看不下去了,因此决定用两种方法督促摆烂人。 一是在 位置督促他们打模拟赛,这样会使得所有 的 位置的摆烂人去打模拟赛而不是摆烂。 二是在 位置督促他们卷文化课,这样会使得所有 的 位置的摆烂人去卷文化课而不是摆烂。
但摆烂人是不能同时被两个任务push的,所以如果一个位置的摆烂人又被督促去打模拟赛又被督促去卷文化课,他就会因为太累而彻底躺平,而这是卷王所厌恶的,所以他不想让这种情况发生。
由于卷王自己也要卷,他不想进行重复劳动,因此在每个位置最多督促摆烂人一次。
由于有些地方的摆烂人会偷袭卷王从而使得卷王花费的时间变成无穷大,因此卷王不会去某些位置督促摆烂人。
卷王想知道他有多少种督促摆烂人的方案,使得每个位置的摆烂人都去打模拟赛或卷文化课,方案不同当且仅当在某个位置上的操作不同(督促打模拟赛/督促卷文化课/什么也不做)。
卷王因为是卷王,所以他一眼就知道了问题的答案,但是为了不让你摆掉,他将问题丢给了你。
由于答案可能很大,输出其对 取模的结果。
输入
第一行一个正整数 。 接下来 行每行一个长度为 的字符串表示第 行的情况。如果第 个字符为 则表示卷王不会到 督促摆烂人,字符只可能为 或 。
输出
输出可能的方案数对 取模后的结果
3
WWW
.WW
..W
5
见附件中的sample.in
见附件中的sample.out
数据范围
本题共 组数据。
对于 的数据,。
对于 的数据,。
对于 的数据,。