4-cycle (Hard)

$N$개의 정점과 $M$개의 무방향 간선으로 이루어진 단순 그래프 $G$가 주어진다. 단순 그래프란, 두 정점 사이에는 최대 $1$개의 간선이 존재하고, 모든 간선이 서로 다른 두 정점을 연결하는 그래프이다. $G$의 정점들은 $N$ 이하의 양의 정수들로 번호가 매겨져 있다.

그래프 $G$의 길이가 $L$인 단순 사이클은 다음 조건을 만족하는 정점의 수열 $\left( v\_0,v\_1,\cdots ,v\_L \right)$로 정의된다.

• 모든 $0\leq i\<L$인 $i$에 대해 $v\_i$와 $v\_{i+1}$을 연결하는 간선이 $G$에 존재한다.
• 모든 $0\leq i\<j\<L$인 $i,j$에 대해 $v\_i\neq v\_j$를 만족하고, $v\_L=v\_0$이다.

이때, 두 단순 사이클이 다음의 연산을 이용해 서로 변환 가능하면, 이를 동일한 사이클로 간주한다.

• 수열을 뒤집는다. 즉, $\left( v\_0,v\_1,\cdots ,v\_L \right)$을 $\left( v\_L,\cdots ,v\_1,v\_0 \right)$로 변경한다.
• 수열의 두 번째 원소를 맨 뒤에 추가하고 첫 번째 원소를 삭제한다. 즉, $\left( v\_0,v\_1,\cdots ,v\_L \right)$을 $\left( v\_1,\cdots ,v\_L,v\_1 \right)$로 변경한다.

예를 들어, 단순 사이클 $\left( 1,2,3,4,1 \right)$과 $\left( 2,1,4,3,2 \right)$는 동일한 단순 사이클이다. 주어진 그래프 $G$에서 길이가 $4$인 서로 다른 단순 사이클의 개수를 구해보자.

첫 번째 줄에 그래프 $G$의 정점의 개수 $N(2\leq N\leq 10^5)$과 간선의 개수 $M(1\leq M\leq 10^5)$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$줄에 걸쳐 그래프 $G$의 간선을 이루는 서로 다른 두 정점 $u,v(1\leq u,v\leq N)$가 공백으로 구분되어 주어진다.

간선이 중복으로 들어오지 않음이 보장된다.

그래프 $G$에서 길이가 $4$인 서로 다른 단순 사이클의 개수를 $10^9+7$로 나눈 나머지를 출력한다.

단, $10^9+7$은 소수이다.