육각형 영역

육각형 타일로 이루어진 칸들이 무한하게 놓여 있고, 재현이는 이 중 "시작 칸"이라고 부르는 칸 위에 서 있다. 두 칸은 모서리를 공유하면 이웃하고 있다고 하자. 재현이는 매번 다음 그림과 같이, 1부터 6까지 번호가 붙은 방향 을 따라서 이웃한 칸 중 하나로 이동할 수 있다.

재현이가 총 $N$ 번 움직였을 때 만드는 칸들로 이루어지는 경로는 영역을 형성한다. $i$ 번째 움직일 때는 $D\[i]$ 방향으로 $L\[i]$ 칸을 이동한다. 이 경로는 다음과 같은 특징이 있다.

이 경로는 닫혀있는데, 마지막에 도착하는 칸은 시작 칸과 동일하다는 뜻이다.
이 경로는 단순한데, 맨 처음 시작한 칸만 빼고 모든 칸은 최대 한 번 방문한다는 뜻이다. 맨 처음 시작한 칸은 맨 마지막까지 합쳐서 정확하게 두 번 방문한다.
이 경로는 드러나 있는데, 경로에 포함되는 모든 칸은 최소한 한 개의 경로에 포함되지 않으면서 내부에 있지 않는 칸과 이웃한다.
- 만약 어떤 칸이 경로에 포함되지 않으면서, 경로에 포함되는 칸을 지나지 않고 방문할 수 있는 칸의 개수가 유한하다면 이 칸은 내부에 있다고 한다.

다음은 재현이가 갈 수 있는 경로 중 하나의 예이다.

1번 칸 (핑크색)이 시작 (그리고 마지막) 칸이다.
옅은 파란색 칸들은 경로에 포함되는 칸들이며, 방문 순서가 칸 안에 쓰여 있다.
x표시가 되어 있는 짙은 파란색 칸들은 내부에 있는 칸들이다.

형성된 영역은 경로에 포함되거나, 내부에 있는 모든 칸들로 이루어진다. 영역 안의 칸 $c$ 의 거리는 영역 안의 칸들 만 방문해서 시작 칸부터 칸 $c$ 에 도착할 때까지 필요한 움직임의 최소값이다. 영역 안의 칸에 대한 점수는 $A + d \times B$ 인데, $A$ 와 $B$ 는 재현이가 미리 정한 상수값이며, $d$ 는 이 칸의 거리이다. 다음은 위 예제의 경로에 의 해 형성된 영역 안의 각 칸들의 거리를 보여준다.

재현이가 $N$ 번 움직일 때 만드는 칸들로 이루어진 경로에 의해 형성된 영역의 모든 칸의 점수의 총합을 구하는 프로그램을 작성하시오. 점수의 총합은 매우 큰 값일 수 있으므로, 이 값을 $10^9 + 7$ 으로 나눈 나머지를 구하시오.

육각형 영역

문제

제한