Суперпозиция

Гиптопод Поликарп – существо, прибывшее то ли из будущего, то ли из другого измерения, предоставил человечеству какой-то аппарат, который является то ли квантовым компьютером, то ли вечным двигателем.

Точнее, пока лишь он предоставил схему этого аппарата. На схеме присутствуют N точек и M каналов. Каждый канал соединяет ровно две точки и имеет заряд: «+» или «-». На некоторых каналах заряд находится в суперпозиции «?», то есть пока неизвестен.

Гиптопод Поликарп очень любит циклы, поэтому загадал загадку: сколькими способами можно установить все неизвестные заряды, чтобы все простые циклы на схеме были отрицательными?

Простым циклом на схеме называется последовательность различных точек таких, что все соседние точки, а также первая и последняя, соединены существующим каналом, и каждый канал используется не более одного раза.

Простой цикл является отрицательным, если произведение зарядов каналов этого цикла даёт знак «-».

Поликарп понимает, что ответ может быть слишком большим, поэтому просит вывести его остаток от деления на число 111111111111111111 ((10¹⁸−1)/9).

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

Первая строка входного файла INPUT.TXT содержит два целых числа N и M – количество точек и каналов на схеме соответственно (1 ≤ N, M ≤ 2∙10⁵).

Следующие M строк содержат описания каналов в виде пары целых чисел a_i и b_i (1 ≤ a_i, b_i ≤ N, a_i≠b_i), обозначающих номера точек, которые соединяет этот канал, а также символ, означающий заряд этого канала: «+», «-» или «?».

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

В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.

Примеры

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