NIO is playing a D\&D-like game.

In this game, the map can be concerned as a connected graph with vertices and edges. The vertices are numbered from to and vertex is the destination of his journey. Initially, all edges can be passed in both directions. At the beginning of the game, edges will be randomly selected to become directed edges. All directed edges point to the destination which means he can only approach the destination along the directed edge. In this way, no matter which edge is selected, he can still reach the destination.

But unfortunately, NIO is a road nut. He started at vertex . At each step, he will randomly select an available edge connected with the current vertex and move to the adjacent vertex.

NIO wanted to know how many steps he expected to take to reach the destination.

Since the answer is too large, NIO only wants to know it modulo .

The first line contains three integers , , and  .

Each of the following  lines contains two integers  and  , describing an undirected edge  in the graph

It is guaranteed that the graph is connected and there is at most one edge between any pair of vertices.

A single non-negative integer, denoting the expectation, modulo .

3 1 3
1 2
2 3

3

5 2 4
1 2
2 3
3 4
2 5

332748124