D. Яблов и сложная задача
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тостов придумал очень сложную задачу. Он задал ее Яблову, но Яблов не может ее решить. Вы можете ему помочь?

Дана шахматная доска размера 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'). Эта строка означает, что в клетке на пересечении ai-й строки и bi-го столбца изначально записан символ ci. Все заданные клетки различны.

Считайте, что строки пронумерованы от 1 до n сверху вниз. Аналогично, столбцы пронумерованы от 1 до n слева направо.

Выходные данные

Выведите единственное целое число — ответ на задачу.

Примеры
Входные данные
3 2
1 1 x
2 2 o
Выходные данные
2
Входные данные
4 3
2 4 x
3 4 x
3 2 x
Выходные данные
2
Примечание

В первом тестовом примере существует два способа:


    xxo          xoo
    xox          ooo
    oxx          oox