← 返回题目列表

Codeforces · 461/D

D. Appleman 和复杂的任务

中文机器翻译题面 查看原题

Toastman 提出了一项非常复杂的任务。他把它交给阿普尔曼,但阿普尔曼不知道如何解决。你能帮助他吗?

给定一个 n × n 棋盘。棋盘上的每个单元格要么有字符“x”,要么有字符“o”,要么什么也没有。有多少种方法可以用“x”或“o”(每个单元格最后只能包含一个字符)填充所有空单元格,使得每个单元格中带有“o”的相邻单元格的数量为偶数?求以 1000000007 (109 + 7) 为模的路数。如果板上的两个单元共享一侧,则它们是相邻的。

输入

第一行包含两个整数 n, k (1 ≤ n, k ≤ 105) — 棋盘的大小以及最初包含字符的单元格数量。

接下来是 k 行。第 i 行包含两个整数和一个字符:ai、bi、ci(1 ≤ ai,bi ≤ n;ci 为“o”或“x”)。该行的意思是:单元格中有一个字符ci,位于第ai行和第bi列的交点处。所有给定的单元格都是不同的。

考虑行从上到下编号为 1 到 n。类似地,列从左到右编号为 1 到 n。

输出

打印一个整数——问题的答案。

示例

输入 #1

3 2
1 1 x
2 2 o

输出 #1

2

输入 #2

4 3
2 4 x
3 4 x
3 2 x

输出 #2

2

注意

在第一个示例中有两种方法: