Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Woods

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


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"