Задача  Woods

Фермеры - герои задач Garden и NewGarden снова получили в совместное  владение сад прямоугольной формы размером 2*N,  разделенный тропинками на одинаковые квадратные участки 1*1. На этот раз было решено выращивать  фруктовые дерева. У фермеров имеется достаточное количество саженцев K видов, среди которых есть мешающие друг другу, если их сажать на соседних (имеющих общую сторону) участках. Чтобы фруктовые деревья плодоносили,  на каждом участке нужно сажать ровно  по одному дереву, и  на  соседних участках не должны расти "мешающие" деревья. Помогите фермерам подсчитать количество способов посадки деревьев так, чтобы они все плодоносили.

Технические условия. Программа  Woods читает с клавиатуры через пробелы целые числа  N и К  (1<=N<=100, 2<=K<=5),  далее количество пар видов деревьев, которые нельзя сажать на соседних участках S (0<=S<K*(K+1)/2), далее S пар номеров видов деревьев. Никакая пара не повторяется. Возможно, что одинаковые деревья мешают друг другу.   Программа выводит на экран   искомое количество способов по модулю 2010.

Примеры

Ввод 3 2 0

Вывод 64

Ввод 2 4 4 2 2 1 2 1 3 3 4

Вывод 37