BOJ 20951 유아와 곰두리차

문제 링크:

문제 내용

$N$개의 정점과 $M$개의 양방향 간선으로 이루어진 그래프가 있습니다. 이 그래프 위에서 길이 7인 경로의 개수를 구하세요.

경로의 길이는 경로에 포함된 간선의 개수를 의미합니다. 하나의 경로는 같은 정점이나 같은 간선을 여러 번 포함할 수 있습니다.

입력

첫 번째 줄에 $N$과 $M$이 주어집니다. ($2 \le N \le 100\;000$, $1 \le M \le \min(\frac{N(N-1)}{2}, 100\;000)$)

다음 $M$줄에 걸쳐서 각 간선의 양 끝점 $u$, $v$가 주어집니다. ($1 \le u, v \le N$, $u \neq v$)

중복된 간선은 주어지지 않습니다.

출력

문제의 정답을 $10^9+7$로 나눈 나머지를 출력합니다.

문제 풀이