CF461D Appleman and Complicated Task

Toastman 想出了一个非常复杂的任务。他将其交给 Appleman，但 Appleman 不知道如何解决。你能帮助他吗？ 给定一个 $n \times n$ 的棋盘，每个格子上要么有字符 'x'，要么有字符 'o'，要么什么都没有。请问有多少种方法可以为所有空白的格子填入 'x' 或 'o'（最终每个格子只能包含一个字符），使得对于每一个格子，它相邻格子中含有 'o' 的格子的数量都是偶数？请将答案对 $1000000007$（即 $10^{9}+7$）取模输出。若两个格子共享一条边，则它们相邻。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 10^{5}$），表示棋盘的大小和初始已有字符的格子数量。 接下来的 $k$ 行，每行包含两个整数和一个字符：$a_i$、$b_i$、$c_i$（$1 \leq a_i, b_i \leq n$，$c_i$ 为 'o' 或 'x'）。表示第 $a_i$ 行第 $b_i$ 列的格子中已经填入了字符 $c_i$。所有给定的格子互不相同。 棋盘的行编号为 $1$ 到 $n$，自上而下；列编号为 $1$ 到 $n$，自左而右。

输出一个整数，表示满足条件的填法总数。

在第一个样例中，共有两种填法： `

xxo xoo

xox ooo

oxx oox

` 由 ChatGPT 5 翻译