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
注意
在第一个示例中有两种方法: