4-사이클 (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$인 서로 다른 단순 사이클의 개수를 구해 보자.

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

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

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

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

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