Appleman and Complicated Task

题意翻译

给定一个 $ n\times n $ 的一部分,其中 $ k $ 个位置已经被填充为 $ O $ 或 $ X $ . 求有多少种填充剩下的位置为 $ O $ 或 $ X $ 的方式,使得任意位置四周的 $ O $ 的数量均为偶数. - $ O $ 和 $ X $ 的数量均是无限制的,你可以填充任意个. - 偶数指可以被 $ 2 $ 整除的自然数. - 对于一个位置 $ (A,B) $,它的四周的位置为 $ (A-1,B) $ , $ (A+1,B) $ , $ (A,B-1) $ , $ (A,B+1) $. 答案对 $ 1000000007 $ 取模. 行从上到下依次为 $ 1,2,3,4,\dots,n $ .同样地,列从左到右依次为 $ 1,2,3,4,\dots,n $ . #### 样例#1解释: ##### 初始图 ``` x?? ?ox ??? ``` ##### 第一种方式 ``` xxo xox oxx ``` ##### 第二种方式 ``` xoo ooo oox ```

题目描述

Toastman came up with a very complicated task. He gives it to Appleman, but Appleman doesn't know how to solve it. Can you help him? Given a $ n×n $ checkerboard. Each cell of the board has either character 'x', or character 'o', or nothing. How many ways to fill all the empty cells with 'x' or 'o' (each cell must contain only one character in the end) are there, such that for each cell the number of adjacent cells with 'o' will be even? Find the number of ways modulo $ 1000000007 $ $ (10^{9}+7) $ . Two cells of the board are adjacent if they share a side.

输入输出格式

输入格式

The first line contains two integers $ n $ , $ k $ ( $ 1<=n,k<=10^{5} $ ) — the size of the board, and the number of cells that has characters initially. Then $ k $ lines follows. The $ i $ -th line contains two integers and a character: $ a_{i} $ , $ b_{i} $ , $ c_{i} $ ( $ 1<=a_{i},b_{i}<=n $ ; $ c_{i} $ is either 'o' or 'x'). This line means: there is a character $ c_{i} $ in the cell that is located on the intersection of the $ a_{i} $ -th row and $ b_{i} $ -th column. All the given cells are distinct. Consider that the rows are numbered from $ 1 $ to $ n $ from top to bottom. Analogically, the columns are numbered from $ 1 $ to $ n $ from left to right.

输出格式

Print a single integer — the answer to the problem.

输入输出样例

输入样例 #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

说明

In the first example there are two ways: `<br></br> xxo xoo<br></br> xox ooo<br></br> oxx oox<br></br>`