Задача 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