## DMOPC '15 Contest 3 P6 - Gala

View as PDF

Points: 30 (partial)
Time limit: 1.0s
PyPy 2 2.0s
PyPy 3 2.0s
Memory limit: 128M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

All the DMOJ admins have come together to organize the Don Mills Programming Gala, an event where contestants come to Don Mills C. I. and show off their programming skills! The organizers have discovered that, this year, everybody is competing in a pair. To help organize the Gala, Xyene will draw a diagram of which contestants are partners.

On Xyene's diagram, there are dots on a line representing the contestants, which have been numbered from on the left to on the right. No two points are on top of each other, and is always even. Xyene can use a compass to connect pairs of dots in the diagram by drawing a perfect semicircle which begins at one dot and ends at another. These semicircles can only be drawn strictly above the line of points.

k_53P drew semicircles in red ink such that no two intersect. Xyene is able to erase any subset of the semicircles drawn in red, but he is only able to draw new semicircles in gray.

What is the number of distinct ways to complete Xyene's diagram? We will consider the diagram complete only if there are semicircles drawn, every point has been connected to a different point, and no two semicircles intersect with each other. Two ways are considered distinct if two points are connected in one way while they are not in the other, or if two points are connected with the colour red in one way while they are connected with gray in the other.

#### Constraints

For all cases,

is an even number.

No two semicircles initially given will intersect with each other.

Note: PyPy 2 and PyPy 3 both have a time limit of 2 seconds.

#### Input Specification

The first line will contain a single integer, .

The following line will contain a single integer, .

The following lines will each contain two space-separated integers, and , where and represents a red semicircle which connects point to point . It is guaranteed that all values of and will be distinct, and that no two semi-circles will intersect.

#### Output Specification

Output a single integer, the number of ways to complete the diagram modulo .

#### Sample Input 1

6
1
1 6

#### Sample Output 1

7

#### Explanation for Sample 1

There are six points on the line, with one semicircle already drawn from point (the leftmost point) to point (the rightmost point). If we do not erase this initial semicircle, then there are two ways to complete the diagram. If we do erase it, then there are five ways.

#### Sample Input 2

4
1
1 3

#### Sample Output 2

2

#### Explanation for Sample 2

There is no way to complete the diagram if we do not erase the part already drawn. Points and cannot be connected without intersecting with the connection between and . Therefore, we must erase the initially drawn semicircle, and this creates ways to complete the diagram.

#### Sample Input 3

6
2
1 2
3 4

#### Sample Output 3

10

#### Explanation for Sample 3

There are four cases: erase nothing for way to complete the diagram, erase only the left semicircle for ways, erase only the right semicircle for ways, or erase them both for ways. This results in ways.

#### Sample Input 4

2
0

#### Sample Output 4

1