시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
20 초 512 MB 27 3 2 18.182%

문제

Fox Ciel is practicing miniature golf, a golf game played with a putter club only. For improving golf skills, she believes it is important how well she bounces the ball against walls.

The field of miniature golf is in a two-dimensional plane and surrounded by \(N\) walls forming a convex polygon. At first, the ball is placed at \((s_x, s_y)\) inside the field. The ball is small enough to be regarded as a point.

Ciel can shoot the ball to any direction and stop the ball whenever she wants. The ball will move in a straight line. When the ball hits the wall, it rebounds like mirror reflection (i.e. incidence angle equals reflection angle).

For practice, Ciel decided to make a single shot under the following conditions:

  • The ball hits each wall of the field exactly once.

  • The ball does NOT hit the corner of the field.

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

입력

The input contains several datasets. The number of datasets does not exceed \(100\). Each dataset is in the following format.

N
sx sy
x1 y1
:
:
xN yN

The first line contains an integer \(N\) (\(3 \leq N \leq 8\)). The next line contains two integers \(s_x\) and \(s_y\) (\(-50 \leq s_x, s_y \leq 50\)), which describe the coordinates of the initial position of the ball. Each of the following \(N\) lines contains two integers \(x_i\) and \(y_i\) (\(-50 \leq x_i, y_i \leq 50\)), which describe the coordinates of each corner of the field. The corners are given in counterclockwise order. You may assume given initial position \((s_x, s_y)\) is inside the field and the field is convex.

It is guaranteed that there exists a shoot direction for each valid order of the walls that satisfies the following condition: distance between the ball and the corners of the field \((x_i, y_i)\) is always greater than \(10^{-6}\) until the ball hits the last wall.

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

출력

For each dataset in the input, print the number of valid orders of the walls in a line.

예제 입력

4
0 0
-10 -10
10 -10
10 10
-10 10
0

예제 출력

8

힌트