Сколько таблиц истинности подходит

Есть n логических переменных x1, x2, ..., xn, каждая принимает значение 0 или 1. Задано m условий двух типов.

Каждое условие задаётся тройкой a b t:

• если t = 1, то должно быть истинно (x_a → x_b). Импликация (p → q) ложна только в случае p = 1 и q = 0, во всех остальных случаях она истинна;
• если t = 0, то должно быть истинно (x_a ∨ x_b).

Найдите, сколько наборов значений (x1, x2, ..., xn) удовлетворяют одновременно всем m условиям.

Формат ввода:

• Первая строка: два целых числа n и m.
• Далее m строк: по три целых числа a, b, t.

Формат вывода:

• Одно целое число — количество подходящих наборов.

Ограничения:

• 1 ≤ n ≤ 14
• 0 ≤ m ≤ 200
• 1 ≤ a, b ≤ n
• t ∈ {0, 1}

Пример: Ввод:

2 2
1 2 1
1 2 0

Вывод:

2