2390번 - ⎐

문제

무방향 단순 그래프 $G$가 주어질 때, $G$의 부분 그래프 중 아래 그림과 같은 ⎐ (U+2390) 모양의 그래프와 동형인 것의 개수를 10ドル^9+7$로 나눈 나머지를 구하여라. 두 부분 그래프는 이루고 있는 간선의 집합이 다를 때만 다른 것으로 센다.

입력

첫째 줄에 $G$의 정점의 개수 $N$과 간선의 개수 $M$이 공백을 사이에 두고 주어진다. $(1 \le N,M \le 239,000)$

다음 $M$개의 줄에 간선으로 연결된 두 정점의 번호 $x, y$가 공백을 사이에 두고 주어진다. $(1 \le x,y \le N)$

$G$의 각 정점에는 1ドル$번부터 $N$번까지의 서로 다른 번호가 매겨져 있다.

출력

$G$의 부분 그래프 중 ⎐ 모양의 그래프와 동형인 것의 개수를 10ドル^9+7$로 나눈 나머지를 출력한다.

제한

힌트