Loading repovive.com/contests/14/problems/F
| # | Title | Points | Solved | Admin | |
|---|---|---|---|---|---|
You are given closed intervals on the real line. The endpoints of every interval are integers between and .
A permutation of the intervals is called good if for every with , the union of intervals is connected.
Equivalently, for every prefix, the union must be a single closed interval on the real line.
For each test case, count the number of good permutations modulo .
There is only one interval, so the only permutation is good.
After both intervals are chosen, the union contains two separate points and is not connected. Therefore no permutation is good.
Every two intervals intersect, so any order keeps every prefix connected. There are good permutations.
If is first, the other two intervals can be placed in any order. If a single-point interval is first, must be second. This gives good permutations.
There are permutations in total. The only bad ones are the four permutations where and are the first two intervals in either order, because the second prefix is disconnected. So the answer is .