Олимпиадный тренинг

Задача . D. Яблов и сложная задача


Задача

Темы: математика снм *2800

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

Дана шахматная доска размера 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 слева направо.

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

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

Примечание

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


    xxo          xoo
    xox          ooo
    oxx          oox

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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет