The Flights

Limits: 2 sec., 256 MiB

John and Brus recently bought several small airplanes. And now they want to make some money by holding some flights. There are \(N\) cities with airports and it’s possible to hold a flight from any city to any other. Somehow Brus found out that the most efficient way is to hold \(N\) flights in such way that for each city there is exactly one incoming and one outgoing flight.

John: What is this button for?

Brus: Damn, I’ve forgotten my parachute!

Some cities are connected by two-way roads. There can be more than one road between two cities. Two cities are called connected if it’s possible to get from one city to another by roads (possibly via some other cities). John thinks that it’s too silly to hold a flight between two connected cities. Thus he wants to assign all \(N\) flights in such way that there will be no flights between connected cities. You have to calculate the number of flight assignments that satisfy John’s condition modulo \(1234567891\).

Input

A test case starts with a line containing two integers \(N\) and \(M\) — the number of cities and the number of roads respectively. Each of next \(M\) lines contains two different integers \(A_i\) and \(B_i\) — the cities connected by \(i\)-th road. All the integers in a single line are separated by single spaces.

Output

Print a single line containing the number of flight assignments satisfying John’s condition modulo \(1234567891\).

Constraints

\(1 \le N \le 1000\),

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

\(1 \le A_i, B_i \le N\).

Samples