Pak Dengklek's Hexagonal Territory

Pak Dengklek stands on an infinite plane tiled with regular hexagons. He designates the cell he stands on as the initial cell. Two hexagons that share a common edge are considered adjacent. In one move, Pak Dengklek can move from a cell to one of its six neighboring cells in one of the six directions, numbered from \(1\) to \(6\) (as shown in the figure).

He performs a sequence of \(N\) actions. In the \(i\)th action, he moves in direction \(D[i]\) for \(L[i]\) steps. The path produced by his moves (i.e. the sequence of cells visited in order) satisfies the following properties:

• Closed: The starting cell and the ending cell (i.e. the initial cell) are identical.
• Simple: Except for the initial cell (which appears twice, as the start and the end), every other cell is visited at most once.
• Exposed: For every cell on the path, there is at least one adjacent cell (sharing an edge) which is not in the path and is not an internal cell. A cell that is not in the path is called an internal cell if, starting from it and moving only through cells not in the path, one can only reach finitely many cells.

The "territory" constructed consists of every cell on the path plus all the internal cells. In the territory, the distance \(d(c)\) of a cell \(c\) is defined as the minimum number of moves required to reach \(c\) from the initial cell, if one is restricted to moving only through cells in the territory. Each cell \(c\) is assigned a score as follows:

[ \text{score}(c) = A + B \times d(c), ]

Given the sequence of moves, compute the sum of scores over all cells in the territory, modulo \(10^9+7\).

You are to implement the function

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

where \(N\) is the number of moves, \(A\) and \(B\) are the scoring constants, and arrays \(D\) and \(L\) each have size \(N\), representing the direction and number of steps for each move. The function should return the total score modulo \(10^9+7\).

inputFormat

The input is given in the following format:

N A B
D[0] D[1] ... D[N-1]
L[0] L[1] ... L[N-1]

Where:

• N is the number of moves.
• A and B are integers used in computing the score.
• The next line contains \(N\) integers, the elements of array D (each in the range 1 to 6).
• The last line contains \(N\) integers, the elements of array L.

outputFormat

Output a single integer: the sum of scores of all cells in the territory, modulo \(10^9+7\).

sample

3 1 1
1 3 5
1 1 1

5