Putter

Time limit8sMemory limit512 MB

Summary

Count the orders in which a single bouncing shot from inside a convex polygon can hit each wall exactly once.

Level: Hard8 of 10
Topics: Geometry, Brute force
Solved: No attempts yet

Problem

Fox Ciel practises miniature golf, a golf game played with a putter only. She thinks that bouncing the ball off the walls well is what improves her golf skills.

The course lies in a two dimensional plane and is surrounded by $N$ walls that form a convex polygon. The ball starts at the point $(s_x, s_y)$ inside the course. The ball is small enough to be treated as a point.

Ciel can shoot the ball in any direction and can stop the ball whenever she wants. The ball moves in a straight line. When the ball hits a wall it bounces like a mirror reflection, so the angle of incidence equals the angle of reflection.

Ciel makes a single shot that satisfies both of the following conditions.

The ball hits each wall of the course exactly once.
The ball never hits a corner of the course.

Count the number of possible orders in which the ball hits the walls.

Input

The input contains several datasets. The number of datasets is at most 100. Each dataset has the following format.

N
sx sy
x1 y1
:
:
xN yN

The first line contains an integer $N$ ( $3 \le N \le 8$ ). The second line contains two integers $s_x$ and $s_y$ ( $-50 \le s_x, s_y \le 50$ ), the coordinates of the initial position of the ball. Each of the next $N$ lines contains two integers $x_i$ and $y_i$ ( $-50 \le x_i, y_i \le 50$ ), the coordinates of one corner of the course. The corners are given in counterclockwise order. The initial position $(s_x, s_y)$ is inside the course, and the course is convex.

For every valid order of the walls there is a shooting direction such that the distance between the ball and every corner $(x_i, y_i)$ stays greater than $10^{-6}$ until the ball hits the last wall.

The last dataset is followed by a line containing a single zero.

Output

For each dataset, print the number of valid orders of the walls on one line.

Examples2

Example 1
Input
```
4
0 0
-10 -10
10 -10
10 10
-10 10
0
```
Expected output
```
8
```

Example 2

Input

Expected output

6
10