육각형 영역

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

재현이가 총 $N$번 움직여 만드는 칸들의 경로는 영역을 형성한다. $i$번째 움직일 때는 $D[i]$ 방향으로 $L[i]$칸을 이동한다. 이 경로에는 다음 특징이 있다.

• 경로는 닫혀 있다. 마지막에 도착하는 칸이 시작 칸과 같다.
• 경로는 단순하다. 시작 칸을 제외한 모든 칸은 최대 한 번 방문한다. 시작 칸은 처음과 마지막을 합쳐 정확히 두 번 방문한다.
• 경로는 드러나 있다. 경로에 포함되는 모든 칸은 경로에 포함되지 않으면서 내부에 있지 않은 이웃 칸을 최소한 하나 가진다.
  • 경로에 포함되지 않은 칸에서 출발해 경로에 포함된 칸을 지나지 않고 방문할 수 있는 칸의 개수가 유한하면, 그 칸은 내부에 있다고 한다.

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

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

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

다음은 위 경로가 만든 영역 안의 각 칸의 거리를 보여준다.

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

• $3 \le N \le 200\,000$
• $0 \le A, B \le 10$
• $1 \le D[i] \le 6$ (모든 $0 \le i \le N - 1$)
• $1 \le L[i]$ (모든 $0 \le i \le N - 1$)
• $L$의 모든 원소의 합은 $10^9$을 넘지 않는다.