그래프 변환

$x_i$를 그래프를 $i$번 변환했을 때의 정점 개수로 정의하겠습니다.

$y_i$를 그래프를 $i$번 변환했을 때 한 정점이 가진 간선의 개수로 정의하겠습니다.

그래프를 변환하더라도 정점 간의 대칭이 유지되기 때문에 각 정점이 가진 간선의 개수는 항상 동일합니다.

$x_0 = n$, $y_0 = n - 1$입니다.

정점이 $x$개인 그래프($G$)에서 정점 하나에 $y$개의 간선을 가진 그래프가 가진 간선의 총 개수는 악수 정리에 의해 $(x y)/2$입니다.

모든 간선은 새로운 그래프($G'$)의 정점이 되므로 $x(i+1)=(x_i y_i)/2$입니다.

계산 과정에서 $1/2 \equiv 5 \dot 10^8+4 \space (mod \space 10^9+7)$임을 이용할 수 있습니다.

한 정점이 $y$개의 간선을 가졌을 때, 특정 간선을 기준으로 보면 양쪽에 $y-1$개씩의 간선이 인접해 있습니다.

따라서 새로운 그래프($G'$)의 각 정점은 $2(y-1)$개의 간선을 가지므로 $y(i+1)=2(y_i-1)$입니다.

위 정보를 바탕으로 $x_k$를 구하면 $cal(O)(n)$의 시간복잡도로 문제를 해결할 수 있습니다.