Суперпозиция
(Время: 3 сек. Память: 32 Мб Сложность: 77%)
Гиптопод Поликарп – существо, прибывшее то ли из будущего, то ли из другого измерения, предоставил человечеству какой-то аппарат, который является то ли квантовым компьютером, то ли вечным двигателем.
Точнее, пока лишь он предоставил схему этого аппарата. На схеме присутствуют N точек и M каналов. Каждый канал соединяет ровно две точки и имеет заряд: «+» или «-». На некоторых каналах заряд находится в суперпозиции «?», то есть пока неизвестен.
Гиптопод Поликарп очень любит циклы, поэтому загадал загадку: сколькими способами можно установить все неизвестные заряды, чтобы все простые циклы на схеме были отрицательными?
Простым циклом на схеме называется последовательность различных точек таких, что все соседние точки, а также первая и последняя, соединены существующим каналом, и каждый канал используется не более одного раза.
Простой цикл является отрицательным, если произведение зарядов каналов этого цикла даёт знак «-».
Поликарп понимает, что ответ может быть слишком большим, поэтому просит вывести его остаток от деления на число 111111111111111111 ((1018−1)/9).
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и M – количество точек и каналов на схеме соответственно (1 ≤ N, M ≤ 2∙105).
Следующие M строк содержат описания каналов в виде пары целых чисел ai и bi (1 ≤ ai, bi ≤ N, ai≠bi), обозначающих номера точек, которые соединяет этот канал, а также символ, означающий заряд этого канала: «+», «-» или «?».
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3 3
1 2 ?
2 3 ?
3 1 ? | 4 |
2 | 4 4
1 2 +
1 3 +
2 3 -
1 4 ? | 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|