Despite hewmatt10's escape plan, [REDACTED] has caught up to him! Backed into a corner, hewmatt10's only choice now is to wage war.

The battlefield is a sprawling plateau with ~N~ towers. Some towers are connected by bridges and in total, ~M~ bridges are present.

Letting his inner artist take over, hewmatt10 decides to paint all the towers. In order to make them visually appealing, he decides that no two directly connected towers should be painted the same colour.

But before hewmatt10 can get started, Oscar, hewmatt10's trusty aide, speaks up:

Sir hewmatt10, did you know that if you considered the towers as nodes and the bridges as edges then the battlefield is actually not guaranteed to be a connected graph?

And also, each individual connected component either forms a tree or a graph with a single cycle.

hewmatt10 responds:

No one asked. You're fired now.

Without his trusty aide by his side, he turns to you for help. Can you figure out the number of ways to colour the towers in each component, summed up?

Input Specification

The first line will contain the number of towers, ~N~ ~(0 \le N \le 10^5)~, the number of bridges, ~M~ ~(0 \le M \le 10^5)~, and the number of colours, ~K~ ~(3 \le K \le 10^5)~.

The next ~M~ lines will be in the form of ~u~ ~v~, indicating that towers ~u~ and ~v~ are connected.

Output Specification

You are to output one number, the number of ways to colour the towers in each component, summed up, modulo ~10^9+7~.

Sample Input

8 7 3
1 2
2 3
3 4
4 2
5 6
6 7
6 8

Sample Output

36