| Codeforces Round 309 (Div. 1) |
|---|
| Закончено |
Во многих аниме фигурируют любовные треугольники: Алиса любит Боба, Чарли тоже любит Боба, но Алиса ненавидит Чарли. Вы задумали аниме с n персонажами. Персонажи обозначены числами от 1 от n. Каждая пара персонажей может либо взаимно любить, либо взаимно ненавидеть друг друга (нейтрального состояния нет).
Вы ненавидите любовные треугольники (А и B любят друг друга и B и C любят друг друга, но А и C ненавидят друг друга), а также вы терпеть не можете, когда никто никого не любит. Итак, рассматривая любых трёх человек, вы будете довольны, если ровно одна пара из них любит друг друга (А и B любят друг друга, а C ненавидит и А, и B), либо если все три пары любят друг друга (А любит B, B любит C, C любит А).
Вам дан список из m известных отношений в аниме. Вы точно знаете, что некоторые пары любят друг друга, а некоторые пары ненавидят друг друга. Вам интересно, сколько есть способов доопределить оставшиеся отношения так, чтобы вы были довольны каждым из треугольников. Два способа считаются различными, если два персонажа любят друг друга в одном способе и ненавидят друг друга в другом способе. Выведите это количество по модулю 1 000 000 007.
В первой строке входа записано два целых числа n, m (3 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000).
В следующих m строках записано описание известных отношений. В i-й строке записано три целых числа ai, bi, ci. Если ci равно 1, тогда ai и bi любят друг друга, в противном случае, они ненавидят друг друга (1 ≤ ai, bi ≤ n, ai ≠ bi, 
).
Каждая пара людей описана не более, чем один раз.
Выведите единственное целое число, равное остатку от деления на 1 000 000 007 количества способов заполнения оставшихся пар так, чтобы вы были довольны каждым треугольником.
3 0
4
4 4
1 2 1
2 3 1
3 4 0
4 1 0
1
4 4
1 2 1
2 3 1
3 4 0
4 1 1
0
В первом примере четыре способа таковы:
- Все любят друг друга;
- 1 и 2 любят друг друга, а 3 ненавидит 1 и 2 (а также два симметричных способа).
Во втором примере единственный возможный способ — заставить 1 и 3 любить друг друга, а 2 и 4 — ненавидеть друг друга.
