Польоти

Обмеження: 2 сек., 256 МіБ

Джон і Брюс нещодавно купили декілька малих літаків. І тепер вони хочуть заробити трохи грошей, проводячи польоти.

Є \(n\) міст з аеропортами, з будь-якого міста до будь-якого іншого можна провести рейс. Якимось чином Брюс дізнався, що найефективнішим способом провести \(n\) рейсів є такий, у якому для кожного міста є рівно один вхідний та один вихідний рейс.

Джон: Що робить ця кнопка?

Брюс: Прокляття, я забув свій парашут!

Деякі міста з’єднані двосторонніми дорогами. Між двома містами може бути більше ніж одна дорога. Два міста називаються зв’язними, якщо можливо добратися дорогами з одного міста до іншого (можливо через деякі інші міста). Джон вважає, що проводити рейси між двома зв’язними містами — занадто безглуздо.

Тому він хоче призначити всі \(n\) рейсів таким чином, щоб не було польотів між зв’язними містами.

Вам потрібно порахувати кількість призначень рейсів, які задовольняють умову Джона, за модулем простого числа 1234567891.

Вхідні дані

У першому рядку задано два цілі числа \(n\) і \(m\) — кількість міст і кількість доріг відповідно.

У наступних \(m\) рядках містяться по два різні цілі числа \(a_i\) та \(b_i\) — міста, сполучені \(i\)-ою дорогою

Вихідні дані

Виведіть одне число — кількість призначень рейсів, що задовольняють умову Джона, за модулем 1234567891.

Обмеження

\(1 \le n \le 10^3\),

\(1 \le m \le 10^5\),

\(1 \le a_i, b_i \le n\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 3 1 2 3 4 4 3	4

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
10 0	1334961