Незалежні множини

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

Вам задано граф \(G=(V, E)\), де \(V\) — це множина вершин, а \(E\) — множина ребер.

Множина вершин називається незалежною, якщо будь-які дві вершини із цієї множини не є з’єднаними ребром. За означенням, пуста множина також є незалежною.

На малюнку нижче показано приклад графу та його незалежної множини:

У цій задачі вам потрібно порахувати кількість незалежних множин в обмеженому графі — графі, де ребро між вершиною \(i\) та вершиною \(j\) може існувати лише якщо \(|i-j| \leq 10\).

Вхідні дані

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

Наступні \(m\) рядків описують ребра графу. Кожен рядок містить два цілих числа — номери вершин, які з’єднує відповідне двостороннє ребро.

Вихідні дані

У єдиному рядку виведіть ціле число — кількість незалежних множин за модулем простого числа \(10^9+7\).

Обмеження

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

\(0 \le m \le 10^5\).

Приклади