Вам надано неорієнтований граф, який має \(n\) вершин і \(m\) ребер. Розглядаються підграфи, які мають усі вершини вихідного графа та деякі його ребра.

Підграф називається ейлеровим, якщо кожна вершина має парний степінь.

Ваше завдання порахувати кількість ейлерових підграфів за модулем \(10^9+7\).

Обмеження

• \(1≤n≤10^5\)
• \(0≤m≤2⋅10^5\)
• \(1≤a,b≤n\)

Формат вхідних даних

У першому рядку вхідних даних є два цілі числа \(n\) і \(m\): кількість вершин і ребер. Вершини пронумеровані \(1,2,…,n\).

Після цього є \(m\) рядків, які описують ребра. Кожен рядок має два цілих числа \(a\) і \(b\): між вершиними \(a\) і \(b\) є ребро. Між двома вершинами є щонайбільше одне ребро, і кожне ребро з’єднує дві різні вершини.

Формат вихідних даних

Виведіть кількість ейлерових підграфів за модулем \(10^9+7\).

Приклад вхідних даних

4 3
1 2
1 3
2 3

Приклад вихідних даних

2