

 Task: HollowsThere are two extremely high trees in Byteotia, and each of them has many hollows scooped out in its trunk, one under another. Once upon a time n very fast birds decided to inhabit the hollows. Some of them know each other and therefore would like to be able to pay one another visits in their hollows. The birds fly very fast and always along a straight line. In order to avoid the danger of collision they decided to quarter in a way that:
It is wellknown that birds have very small brains. That's why they have asked you  a respected ornithologist  to help them find out in how many ways they can quarter in the hollows.
TaskWrite a programme that:
InputIn the first line of the standard input there are three integers written n, m and k, denoting respectively: the number of birds, the number of distinct pairs of birds knowing each other and the number that is to be used when giving result (see: Output), 2 <= n <= 1 000 000, 1 <= m <= 10 000 000, 2 <= k <= 2 000 000. The birds are numbered from 1 to n. In the following m lines the pairs of birds knowing each other are given, one per line. In the line no. i + 1 two integers a_{i} and b_{i}, separated by a single space, are written (1 <= a_{i}, b_{i} <= n, a_{i} <> b_{i}). These are the numbers of the familiar birds. Each (unordered) pair of familiar birds is given exactly once.
OutputLet r denote the number of distinct quarterings of birds satysfying the given constraints. Your programme should write one integer in the first line of the standard output: the remainder of division of r by k. If no quartering exists the correst result is 0.
ExampleFor the following input data:3 2 10 1 2 1 3the correct answer is: 4 Print friendly version 