Problem statement정점 $n$개인 무방향 그래프 $G$가 주어진다. 정점이 $k$개인 path $P_k$와의 cartesian product $G \square P_{k}$의 cartesian product의 스패닝 트리의 개수를 구하여라. $n \le 500$, $k \le 10^{18}$.Matrix-tree theorem그래프 $G$의 Laplacian 을 $L_{G} := D_{G} - A_{G}$로 쓰자. $L_{G}$는 real symmetric matrix이고, positive semidefinite이므로 양의 실수 고윳값을 갖는다. Connected graph $G$에 대해 $L_{G}$는 rank $n-1$이 되는데, non-zero eigenvalue를 $\lambda_{1..