В доме Фуада лампочек и электрических выключателей. Выключатели света пронумерованы от до , а лампочки от до . К каждому выключателю можно подключить ноль или более лампочек. Каждая лампочка подключена к двум выключателям.
При переключении выключателя лампочки, подключенные к этому выключателю, гаснут, если они были включены, и включаются, если они были выключены. В настоящее время некоторые лампочки включены, некоторые выключены.
Поскольку Фуад хочет стать инженером-электриком, он решил поиграть с лампочками. Он может переключить каждый выключатель не более одного раза. Фуад хочет переключить несколько выключателей в определенной последовательности, чтобы загорелись все лампочки. Определите, возможно ли это сделать. Если возможно, найдите, сколькими разными способами это можно сделать. Любые два способа считаются разными, если переключение выключателей образует разную последовательность.
Поскольку количество способов может быть большим, найдите остаток от деления ответа на .
Первая строка содержит два целых числа и — количество выключателей и лампочек соответственно. Следующие строк описывает лампы. -ая лампа задается тремя целыми числами и . Известно, что -ая лампа подключена к переключателям с номерами и . указывает на исходное состояние лампы. Если , то лампа горит. Если , то лампа выключена.
Для любых двух выключателей к каждому из них гарантированно подключена не более одной лампочки.
В первой строке выведите yay!, если все лампочки можно включить. В противном случае выведите meh. Во второй строке укажите количество способов включения всех ламп (если это возможно совершить). Поскольку количество способов может быть большим, выведите его остаток от деления на .
В первом примере все лампы можно включить одним из трех способов:
не переключать никаких электрических выключателей;
сначала переключить выключатель номером , затем переключить выключатель с номером ;
сначала переключить выключатель номером , затем переключить выключатель с номером ;
Данная задача состоит из -х подзадач. Баллы за подзадачу начисляются только в случае успешного прохождения всех тестов, связанных с этой подзадачей.
Для каждой подзадачи в этой задаче, если Вы правильно определите, можно или нет просто включить лампочки во всех тестах этой подзадачи, вы получите от балла за эту подзадачу.
( баллов): ;
( баллов): ;
( баллов): нет дополнительных ограничений;