Pak Dengklek đang đứng tại một ô, được gọi là ô xuất phát, trên một lưới hình lục giác vô hạn. Hai ô trong lưới hình lục giác được gọi là lân cận nếu chúng có chung một cạnh. Trong một bước, Pak Dengklek có thể đi từ một ô sang một trong các ô lân cận của nó theo một trong sáu hướng có thể, được đánh số từ \(1\) đến \(6\) như trong hình dưới đây.

{{asset:apio21hexagon/hexagon-directions.png}}

Pak Dengklek sẽ tạo ra một lãnh thổ bằng cách đi theo một lộ trình gồm dãy các ô được thăm bởi \(N\) phép dịch chuyển. Ở phép dịch chuyển thứ \(i\), Pak Dengklek chọn hướng \(D[i]\), sau đó thực hiện \(L[i]\) bước theo hướng đã chọn. Lộ trình có các tính chất sau:

• Lộ trình đóng, nghĩa là ô ở cuối dãy trùng với ô ở đầu dãy.
• Lộ trình đơn, nghĩa là mỗi ô được thăm nhiều nhất một lần, ngoại trừ ô xuất phát được thăm đúng hai lần (lúc bắt đầu và lúc kết thúc).
• Lộ trình lộ ra, nghĩa là mỗi ô trên lộ trình lân cận với ít nhất một ô không nằm trên lộ trình và không nằm bên trong.
• Một ô được gọi là bên trong nếu nó không nằm trên lộ trình và từ ô đó chỉ có thể thăm được hữu hạn ô bằng bất kỳ dãy bước đi nào không đi qua ô nào trên lộ trình.

Dưới đây là một ví dụ về lộ trình Pak Dengklek có thể đi:

• Ô được đánh số \(1\) (tô màu hồng) là ô xuất phát (và kết thúc).
• Các ô được đánh số (tô màu xanh lam nhạt) là các ô trên lộ trình, được đánh số theo thứ tự được thăm.
• Các ô được gạch chéo (tô màu xanh lam đậm) là các ô bên trong.

{{asset:apio21hexagon/hexagon-path.png}}

Lãnh thổ được hình thành gồm tất cả các ô nằm trên lộ trình hoặc nằm bên trong. Khoảng cách của một ô \(c\) trong lãnh thổ là số bước ít nhất cần thiết để đi từ ô xuất phát đến ô \(c\) mà chỉ đi qua các ô trong lãnh thổ. Điểm của một ô trong lãnh thổ được định nghĩa là \(A + d \times B\), trong đó \(A\) và \(B\) là các hằng số do Pak Dengklek xác định trước, còn \(d\) là khoảng cách của ô đó. Hình dưới đây minh họa khoảng cách của mỗi ô trong lãnh thổ được tạo bởi lộ trình ở ví dụ trên.

{{asset:apio21hexagon/hexagon-distances.png}}

Hãy giúp Pak Dengklek tính tổng điểm của tất cả các ô trong lãnh thổ được hình thành bởi \(N\) phép dịch chuyển mà Pak Dengklek sẽ thực hiện. Vì tổng điểm có thể rất lớn, hãy tính kết quả theo modulo \(10^9 + 7\).

Chi tiết cài đặt

Thí sinh cần cài đặt hàm sau:

int draw_territory(int N, int A, int B, std::vector<int> D,
                   std::vector<int> L);

• \(N\): số phép dịch chuyển.
• \(A\), \(B\): các hằng số dùng để tính điểm.
• \(D\): mảng độ dài \(N\), trong đó \(D[i]\) là hướng của phép dịch chuyển thứ \(i\).
• \(L\): mảng độ dài \(N\), trong đó \(L[i]\) là số bước được thực hiện trong phép dịch chuyển thứ \(i\).
• Hàm phải trả về tổng điểm của tất cả các ô trong lãnh thổ theo modulo \(10^9 + 7\).
• Hàm được gọi đúng một lần.

Ví dụ

Xét lời gọi sau:

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});

Các phép dịch chuyển chính là các phép dịch chuyển được minh họa trong phần mô tả. Bảng sau liệt kê điểm của mỗi ô ứng với mọi khoảng cách có thể có trong lãnh thổ.

Tổng điểm là \(2 + 20 + 40 + 66 + 56 + 51 + 80 + 92 + 130 + 87 + 128 + 175 + 76 = 1003\). Vì vậy, hàm draw_territory phải trả về \(1003\).

Ràng buộc

• \(3 \le N \le 200\,000\).
• \(0 \le A, B \le 10^9\).
• \(1 \le D[i] \le 6\) với mọi \(0 \le i \le N - 1\).
• \(1 \le L[i]\) với mọi \(0 \le i \le N - 1\).
• Tổng tất cả các phần tử của \(L\) không vượt quá \(10^9\).
• Lộ trình là đóng, đơn và lộ ra.

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

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

Trình chấm mẫu ghi kết quả theo định dạng sau:

• Dòng \(1\): giá trị trả về của hàm 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

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2021: Hexagonal Territory.