Berland is a modern country, and one could hardly find a man, who would believe evil spirits. Everybody knows that celebrating Halloween is just tribute to old tradition. However, a coach of Berland University student programming teams wants to divide students (3N in total) into teams of three to have as many demonic teams as possible at the moment of future Halloween contest. But he knows for some triples of students that they can't make a demonic team, as they haven't performed well in action in previous contests. He has a list of these K forbidden triples. The coach supposes that any three students can make a demonic team unless they do not form a triple contained in the list. And now he wants to know the number of such partitions that all teams are demonic.

The first line of the input contains two integers N and K, separated by one space (1 ≤ N ≤ 1000, 0 ≤ K ≤ 20). Next K lines contain three integers each a_i, b_i, c_i (1 ≤ i ≤ K, 1 ≤ a_i, b_i, c_i ≤ 3N). All triples are unique, that is they all are diffent as sets, and a_i ≠q b_i, a_i ≠q c_i, b_i ≠q c_i.

The output should contain the only number without leading zeroes — the answer to the task.

sample input	sample output
2 0	10

sample input	sample output
2 3 1 2 3 4 5 6 1 4 5	8