Bridge Construction
Time limit2sMemory limit256 MB
Count unlabeled connected graphs on N vertices with maximum degree at most 4, modulo a prime X.
- Level
Hard8 of 10
- Topics
- Combinatorics, Dynamic programming, Graph, Math
- Solved
- No attempts yet
Problem
Long ago, there was an island nation made of N islands. The islands all had the same shape, so they could not be distinguished from one another.
There were no bridges between the islands, so people had to take boats to travel between them. After some discussion, the residents decided to build bridges connecting the islands.
Since building bridges arbitrarily could lead to a mess, they set three conditions for bridge construction.
- When the bridges are built, all islands must be connected. That is, it must be possible to travel between any two islands using the bridges.
- To save on construction costs, the number of bridges must be minimal.
- Since too many bridges attached to one island could paralyze the traffic network, at most four bridges can be built at one island.
For example, when N=6, the method on the left is a possible construction method, but the method on the right is not.
Find the total number of ways to build the bridges. Assume the islands are indistinguishable.
Input
The first line gives the number of islands N and X. (1 ≤ N ≤ 3000, 109 ≤ X ≤ 109+104, X is prime)
See the output section for what X is used for.
Output
Output the number of ways to build the bridges. Since the answer can be very large, output it modulo X.
Assume the islands are indistinguishable.