Bessie и коровы соседних ферм решили соединить фермы тропами, создав союз против фермеров. Каждой из $N$ ферм ($1 \le N \le 100,000$) поручили построить тропу ровно к одной другой ферме, всего $N$ троп. Но спустя месяцы построены лишь $M$ ($1 \le M < N$).

Споры, какие фермы уже строили тропы, грозят расколоть союз. Bessie хочет посчитать способы строительства существующих $M$ троп, чтобы снять напряжение. Тропу между 3 и 4 могла построить либо ферма 3, либо 4. Найдите число назначений троп построившим их фермам по модулю 1,000,000,007. Назначения различны, если хотя бы одну тропу построили разные фермы.

Входные данные

• Строка 1: целые числа $N$ и $M$ через пробел.
• Строки $2..1+M$: строка $i+1$ описывает тропу $i$ числами $u_{i}$ и $v_{i}$ через пробел ($1 \le u_{i}, v_{i} \le N, u_{i} \ne v_{i}$), соединяемые фермы.

Выходные данные

• Строка 1: число назначений по модулю 1,000,000,007. Если условия невыполнимы, выведите 0.

Примеры

Входные данные 1

5 4
1 2
3 2
4 5
4 5

Выходные данные 1

6

Примечание

Между одной парой ферм могут быть две тропы.

Есть 6 назначений. Пусть $\{a,b,c,d\}$ означает, что ферма 1 строит тропу a, 2 — b, 3 — c, 4 — d. Тогда назначения: $\{2, 3, 4, 5\}$ $\{2, 3, 5, 4\}$ $\{1, 3, 4, 5\}$ $\{1, 3, 5, 4\}$ $\{1, 2, 4, 5\}$ $\{1, 2, 5, 4\}$

Автор задачи: Mark Gordon, 2011