Cactus

Let me be upfront about this: things are not going well. What was supposed to be a relaxing evening with friends took a turn for the worse when you were assaulted by a walking advertisement of cheap cologne, and your Priceless Argentinian Cactus, the only thing you hold dear, was thrown out of the window.

Right after the deed, or as soon as was physically possible, you ran down the stairs to assess the losses. And there it was, your priceless cactus, alive! It had a few scratches, but it was alive. How did this happen? Did it land on something soft? Overwhelmed with joy, you decide not to look for answers. Did I say things are not going well? Scratch that. Everything is great, and it is time to celebrate! The guest of honor, of course, is your green stinging friend.

For those less acquainted with botany, a refresher: a cactus is a connected graph in which each vertex lies on at most one cycle. To add to the festive mood, you decide to color every vertex of your cactus with one of $k$ colors. You want as much freedom as possible, but you must follow the golden rule of cactus coloring: no two adjacent vertices may have the same color.

One coloring seems not enough, so once the colors fade, you will recolor the cactus again and again, using a different coloring each time. But how long can you keep this going? Given the description of your cactus and the number $k$, count the number of correct $k$-colorings of the cactus' vertices. The answer may be very large, so it is enough to compute it modulo $10^9 + 7$.

The first line contains the number of test cases $z$ ($1 \leq z \leq 50000$). The test cases follow.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \leq n \leq 300000$, $0 \leq m \leq 400000$, $2 \leq k \leq 10^9$), where $n$ is the number of vertices, $m$ is the number of edges, and $k$ is the number of colors.

The next $m$ lines each contain two integers $u_i$ and $v_i$ ($1 \leq u_i \neq v_i \leq n$), describing an edge of the cactus. The given graph is guaranteed to be a cactus, and every pair of vertices is connected by at most one edge.

The total number of vertices over all test cases does not exceed $3 \cdot 10^6$, and the total number of edges does not exceed $4 \cdot 10^6$.

For each test case, output a single integer: the number of proper colorings of the cactus' vertices with $k$ colors, modulo $10^9 + 7$.