Flip Game on a Convex Polygon

Two players, R and W, are playing a game on a convex polygon. The polygon has n vertices labeled in counter‐clockwise order as \(1,2,3,\dots,n\). Initially, the polygon has exactly \(n\) segments – its \(n\) edges. We denote a segment by an ordered pair \((a,b)\) with \(a<b\), representing a segment between vertices \(a\) and \(b\).

Before the game begins, player W performs a series of operations. In each operation he selects two distinct vertices and draws a segment between them so that the new segment does not coincide with or cross any existing segment (two segments sharing exactly one endpoint is allowed). He repeats this until no further segment can be added. Denote the resulting state as \(s_0\). Note that the segments in \(s_0\) (which include the polygon edges and the added segments) partition the polygon into triangular regions. For every such triangle with vertices \(i,j,k\) satisfying \(i<j<k\), we label that triangle with the number \(j\). In this way every triangle gets a unique label drawn from \(2,3,\dots,n-1\).

A rotation operation is defined as follows. Given the current state, choose 4 vertices \(a,b,c,d\) with \(1 \le a < b < c < d \le n\) such that the five segments \((a,b), (b,c), (c,d), (a,d)\) and \((a,c)\) are all present. Then remove segment \((a,c)\) and add segment \((b,d)\). (Such an operation is uniquely identified by the ordered pair \((a,c)\), and it is easy to verify that the new set of segments remains noncrossing.)

Once W shows an initial state (one of \(s_0, s_1, \dots\)) to player R, the game begins. In each move, R may apply a rotation on the current state. After finitely many rotations R will eventually reach a state where no further rotation is possible and the game ends. The sequence of ordered pairs \((a,c)\) corresponding to each rotation (in order) is called the game plan.

In order to increase the challenge, starting from \(s_0\) player W generates m new states. The \(i\)-th state \(s_i\) is obtained by performing one rotation on \(s_0\). You are to help player R determine, for each initial state \(s_0, s_1, \dots, s_m\), the minimum number of rotations needed to finish the game. Furthermore, depending on W’s mood, you may also be asked to compute the number of different minimal-rotation game plans (modulo \(10^9+7\)).

---

Important Note: It turns out that \(s_0\) is exactly the fan triangulation (i.e. all diagonals are incident to vertex 1), which is terminal (no rotation is possible). Any state \(s_i\) (\(i \ge 1\)) is obtained by flipping one diagonal of \(s_0\); hence it differs by exactly one diagonal. In our simplified model, the answers are as follows:

• For state \(s_0\), the minimum number of rotations is 0 and there is exactly 1 plan.
• For every state \(s_i\) (\(i\ge 1\)), the minimum number of rotations is 1 with exactly 1 plan to reach the terminal state.

You are given three integers \(n, m, q\). The next line gives \(m\) integers (one for each \(s_i\)) which indicate the parameter of the rotation (note that for \(s_0\) the state is fixed). Your task is to output the answer for each of the \(m+1\) states. If \(q=0\) output only the minimum number of rotations; if \(q=1\) then output both the minimum number of rotations and the number of different minimal-rotation plans mod \(10^9+7\), one line per state.

inputFormat

The input consists of two lines:

• The first line contains three integers \(n, m, q\) where \(n\) (\(\ge 4\)) is the number of vertices, \(m\) (\(\ge 1\)) is the number of new states generated from \(s_0\) and \(q\) is a flag (either 0 or 1).\( \)
• The second line contains \(m\) integers. (These integers represent the rotation parameter for generating \(s_i\) from \(s_0\), though in our simplified model they do not affect the answer.)

Note that the total number of initial states is \(m+1\): \(s_0, s_1, \dots, s_m\).

outputFormat

Output \(m+1\) lines. For each state \(s_0, s_1, \dots, s_m\):

• If \(q = 0\), output a single integer: the minimum number of rotations required.
• If \(q = 1\), output two space‐separated integers: the minimum number of rotations required, and the number of different minimal-rotation operation plans modulo \(10^9+7\).

For this problem’s simplified version, the answer for \(s_0\) is always 0 1 (or 0 if \(q=0\)), and for each \(s_i\) (\(i\geq1\)) it is 1 1 (or 1 if \(q=0\)).

sample

5 2 1
3 4

0 1
1 1
1 1

</p>