Електричні вимикачі

В будинку у Фуада $m$ лампочок та $n$ електричних вимикачів. Вимикачі світла пронумеровані від $1$ до $n$, а лампочки від $1$ до $m$. Кожен вимикач можна підключити нуль або більше лампочок. Кожна лампочка підключена до двох вимикачів.

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

Оскільки Фуад хоче стати інженером-електриком, він вирішив пограти з лампочками. Він може перемикнути кожен вимикач не більше одного разу. Фуад хоче перемкнути кілька вимикачів у певній послідовності, щоб увімкнутися всі лампочки. Визначте, чи це можливо зробити. Якщо можливо, знайдіть, скількома різними способами це можна зробити. Любі два способи вважаються різними, якщо перемикання вимикачів утворює різну послідовність.

Оскільки кількість способів може бути великою, знайдіть остачу від ділення відповіді на $(10^9+7)$.

Вхідні дані

Перший рядок містить два цілих числа $n(2\le n\le 500)$ та $m(1\le m\le n\cdot (n-1)/2)$ — кількість вимикачів і лампочок відповідно. Наступні $m$ рядків описують лампочки. Лампа $i$ задається трьома цілими числами $a_i,b_i(1\le a_i\ne b_i\le n,1\le i\le m)$ та $c_i(0\le c_i\le 1,1\le i\le m)$. Відомо, що лампа $i$ підключена до вимикачів з номерами $a_i$ і $b_i(a_i\ne b_i)$. $c_i$ вказує на початковий стан лампи. Якщо $c_i=1$, то лампа горить. Якщо $c_i=0$, то лампа вимкнена.

Для будь-яких двох вимикачів до кожного з них гарантовано підключено не більше однієї лампочки.

Вихідні дані

У першому рядку виведіть yay!, якщо всі лампочки можна увімкнути. В іншому випадку виведіть meh. У другому рядку вкажіть кількість способів увімкнення всіх лампочок (якщо це можливо здійснити). Оскільки кількість способів може бути великою, виведіть його остачу від ділення на $(10^9+7)$.

Приклади

У першому прикладі всі лампочки можна увімкнути одним з трьох способів:

• не перемикати жодних електричних вимикачів;

• спочатку перемикнути вимикач з номером $1$, потім перемикнути вимикач з номером $2$;

• спочатку перемикнути вимикач з номером $2$, потім перемикнути вимикач з номером $1$;

Оцінювання

Дана задача складається з $3$ підзадач. Бали за підзадачу нараховуються лише у випадку успішного проходження всіх тестів, пов'язаних з цією підзадачею.

Для кожного завдання в цьому завданні, якщо Ви правильно визначите, можна чи ні просто включити лампочки у всіх тестах цієї підзадачі, ви отримаєте $40$ від бала за це підзавдання.

1. ($10$ балів): $h<9$;

2. ($20$ балів): $h<18$;

3. ($70$ балів): $немаєдодатковихобмежень$;