"I'm tired of seeing the same scenery in the world." ---
's world can be simplified as a directed graph with vertices and edges.
A in is an ordered list of vertices for some non-negative integer such that is an edge in for all . A can be empty in this problem.
A in is an ordered list of distinct vertices for some positive integer such that is an edge in for all . All circular shifts of a cycle are considered the same.
satisfies the following property: Every vertex is in at most one cycle.
Given a fixed integer , count the number of pairs modulo such that
are paths;
For every vertex , is in or ;
Let be the number of occurrences of in path . For every vertex of , .
输入格式
The first line contains integers , and ().
Each of the next lines contains two integers and , denoting an edge from vertex to ().
No two edges connect the same pair of vertices in the same direction.
输出格式
Output one integer --- the number of pairs modulo .
