Description

On a plane tiled infinitely with hexagons, Pak Dengklek stands on one cell and calls it the initial cell. If two cells in the hexagonal tiling share a common edge, they are called adjacent cells. In one move, Pak Dengklek can move from one cell to an adjacent cell in one of six possible directions (numbered from $1$ to $6$ as shown in the figure below).

Given an action sequence consisting of $N$ actions, Pak Dengklek can construct a territory from the path it produces (which corresponds to a sequence of visited cells in order). The $i$-th action consists of a moving direction $D[i]$ and a move length $L[i]$ in that direction, and the path must satisfy the following properties:

• The path is closed, meaning that in the cell sequence, the starting cell and the ending cell (i.e., the initial cell) are the same.
• The path is simple, meaning that in the cell sequence, except that the initial cell is visited exactly twice (once as the start and once as the end), every other cell can be visited at most once.
• The path is exposed, meaning that in the cell sequence, every cell is adjacent to at least one non-internal cell that does not appear in the sequence.
  • If a cell does not appear in the cell sequence, and starting from it, without passing through any cell in the sequence, it can reach only finitely many cells (via some number of moves), then we call this cell an internal cell.

The figure below shows an example of a path that satisfies the conditions above. In the figure:

• Cell $1$ (pink) is the initial cell.
• The numbered cells (light blue) form the cell sequence, and the numbers indicate the order in which they are visited.
• The cells marked with crosses (dark blue) are internal cells.

The constructed territory contains all cells on the path and all internal cells. The distance of a cell $c$ in the territory is defined as the minimum number of moves needed to reach $c$ from the initial cell while only passing through cells contained in the territory. The score of a cell in the territory is defined as $A+d \times B$, where $A$ and $B$ are constants given by Pak Dengklek, and $d$ is the distance of that cell in the territory. The figure below shows the distance of each cell in the territory constructed from the example path above.

Help Pak Dengklek compute the sum of scores of all cells in the territory constructed from the given action sequence. Since the total score may be very large, output the result modulo ${10}^9+7$.

You need to implement the following function:

int draw_territory(int N, int A, int B, int[] D, int[] L)

• $N$: the number of actions in the action sequence.
• $A, B$: constants in the score calculation.
• $D$: an array of length $N$, where $D[i]$ is the direction of the $i$-th action.
• $L$: an array of length $N$, where $L[i]$ is the move length of the $i$-th action.
• The function should return the total score of all cells in the territory constructed from the given action sequence, modulo ${10}^9+7$.
• This function will be called exactly once.

Input Format

The sample grader reads input in the following format:

• Line $1$: $N$ $A$ $B$.
• Line $2+i$ ($0 \le i \le N-1$): $D[i]$ $L[i]$.

Output Format

The sample grader prints your answer in the following format:

• Line $1$: the return value of draw_territory.

17 2 3
1 1
2 2
3 2
4 1
5 1
4 1
3 1
2 2
1 3
6 2
2 3
3 1
4 6
5 3
6 3
6 2
1 1

1003

Hint

Sample Explanation

Consider the following call:

draw_territory(17, 2, 3,
			   [1, 2, 3, 4, 5, 4, 3, 2, 1, 6, 2, 3, 4, 5, 6, 6, 1],
			   [1, 2, 2, 1, 1, 1, 1, 2, 3, 2, 3, 1, 6, 3, 3, 2, 1])

This action sequence is the same as the example given in the statement above. The table below lists the score corresponding to each possible distance value in this territory.

The total score is $2+20+40+66+56+51+80+92+130+87+128+175+76=1003$.

Therefore, draw_territory should return $1003$.

Constraints

• $3 \le N \le 2\times {10}^5$.
• $0 \le A,B \le {10}^9$.
• $1 \le D[i] \le 6$ ($0 \le i \le N-1$).
• $1 \le L[i]$ ($0 \le i \le N-1$).
• The sum of elements in $L$ does not exceed ${10}^9$.
• The path corresponding to the given action sequence is guaranteed to be closed, simple, and exposed.

Subtasks

1. (3 points): $N=3$, $B=0$.
2. (6 points): $N=3$.
3. (11 points): The sum of elements in $L$ does not exceed $2000$.
4. (12 points): $B=0$, and the sum of elements in $L$ does not exceed $2\times {10}^5$.
5. (15 points): $B=0$.
6. (19 points): The sum of elements in $L$ does not exceed $2\times {10}^5$.
7. (18 points): $L[i]=L[i+1]$ ($0 \le i \le N-2$).
8. (16 points): No additional constraints.

Translated by ChatGPT 5