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

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

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

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

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

Поликарп понимает, что ответ может быть слишком большим, поэтому просит вывести его остаток от деления на число 111111111111111111.