Easter Eggs
Description
You are taking photos of Easter eggs. There are multiple chicken eggs in a basket, each with a unique color. You have $k$ different colors of paint available.
You take $n$ identical eggs from the basket and paint each one of them with one of the $k$ colors. After painting, you arrange the eggs in a single row and capture a photo of this arrangement. You can repeat this process to create different arrangements of colors in the photos.
Now you want to determine how many different photos you can create. Since this number can be very large, you have decided to apply a set of rules to reduce the count. According to these rules, two arrangements are considered the same if you can swap the positions of egg $a_i$ with egg $b_i$ to transform one arrangement into another. You continue to apply more and more rules until the number of different photos becomes reasonably small. The final set of rules consists of $m$ different rules.
Your task is to calculate the number of different photos after applying each new rule.
The first line contains two integers $n$ and $k$ ($1 \leq n, k \leq 100\,000$), representing the number of eggs and the number of available paint colors, respectively. The second line contains a single integer $m$ ($0 \leq m \leq 100\,000$), indicating the total number of rules applied. Each of the next $m$ lines contains a pair of integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$), representing eggs that can be swapped in each rule.
Output exactly $m + 1$ numbers, where the $j$-th number (ranging from $0$ to $m$) represents the number of different photos when applying the first $j$ rules modulo $10^9+7$.
Input
The first line contains two integers $n$ and $k$ ($1 \leq n, k \leq 100\,000$), representing the number of eggs and the number of available paint colors, respectively. The second line contains a single integer $m$ ($0 \leq m \leq 100\,000$), indicating the total number of rules applied. Each of the next $m$ lines contains a pair of integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$), representing eggs that can be swapped in each rule.
Output
Output exactly $m + 1$ numbers, where the $j$-th number (ranging from $0$ to $m$) represents the number of different photos when applying the first $j$ rules modulo $10^9+7$.
4 2
3
1 2
1 3
1 4
4 2
2
1 2
3 4
16
12
8
5
16
12
9