Vào thế kỷ XIV, việc xây dựng lâu đài trên đảo Trakai sắp bắt đầu. Công việc đầu tiên của kiến trúc sư trưởng là lên kế hoạch xây dựng bức tường thành chính.

Xây dựng một bức tường có thể bảo vệ lâu đài trước mọi cuộc tấn công là điều khó khăn. Để bảo đảm an toàn cho quân đồn trú, kiến trúc sư trưởng đã giới hạn phần nào các phương án thiết kế.

Vì các cuộc tấn công từ giữa hồ ít có khả năng xảy ra hơn các cuộc tấn công từ bờ gần đó, bức tường không cần tạo thành một vòng khép kín. Thay vào đó, tường sẽ nằm trên một đường thẳng và gồm \(N\) đoạn xếp liên tiếp từ đầu này đến đầu kia, được đánh số từ \(1\) đến \(N\). Việc còn lại là chọn chiều cao cho từng đoạn.

Kiến trúc sư trưởng đã chọn hai chiều cao có thể dùng cho mỗi đoạn. Chiều cao của đoạn thứ \(i\) sẽ là \(a_i\) hoặc \(b_i\). Như vậy, còn \(2^N\) phương án xây tường.

Một lâu đài nằm trên đảo nhỏ giữa hồ cũng có những khó khăn riêng. Trong thời tiết giông bão, lâu đài có thể bị ngập. Khi đó, nước đọng phía trên các đoạn tường nếu ở cả hai phía có những đoạn cao hơn ngăn nước thoát ra.

Với một cách chọn chiều cao các đoạn tường, ta quan tâm đến lượng nước đọng lại trên tường sau một cơn bão lớn. Hình dưới đây minh họa trường hợp chiều cao các đoạn từ trái sang phải là \(4,2,1,8,6,2,7,1,2,3\) và mực nước tại từng vị trí là \(4,4,4,8,7,7,7,3,3,3\).

Một cách hình thức, với mỗi \(i=1,2,\ldots,N\), mực nước tại vị trí \(i\) ít nhất bằng \(h\) khi và chỉ khi tồn tại các số nguyên \(l\) và \(r\) sao cho \(l\le i\le r\) và chiều cao các đoạn tường tại vị trí \(l\) và \(r\) đều ít nhất bằng \(h\). Đặc biệt, mực nước tại các vị trí \(1\) và \(N\) luôn bằng chiều cao đoạn tường tương ứng, và mực nước tại một vị trí bất kỳ luôn lớn hơn hoặc bằng chiều cao đoạn tường ở đó. Lượng nước đọng tại vị trí \(i\) bằng hiệu giữa mực nước và chiều cao đoạn tường. Tổng lượng nước đọng là tổng các lượng nước đọng tại các vị trí \(1,2,\ldots,N\).

Hãy tính tổng lượng nước đọng, cộng trên tất cả \(2^N\) phương án xây tường, và in ra kết quả lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\).

Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\).

Dòng thứ ba chứa \(N\) số nguyên \(b_1,b_2,\ldots,b_N\).

Dữ liệu ra

In ra một số nguyên duy nhất là tổng lượng nước đọng trên tất cả \(2^N\) phương án xây tường, lấy modulo \(10^9+7\).

Ràng buộc

• \(1\le N\le 5\cdot 10^5\).
• \(1\le a_i,b_i\le 10^9\) và \(a_i\ne b_i\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(8\) điểm: \(N\le 20\).
2. \(17\) điểm: \(N\le 100\) và \(a_i,b_i\le 1000\) với mọi \(1\le i\le N\).
3. \(19\) điểm: \(N\le 10\,000\) và \(a_i,b_i\le 1000\) với mọi \(1\le i\le N\).
4. \(14\) điểm: \(N\le 10\,000\).
5. \(12\) điểm: \(a_i,b_i\le 2\) với mọi \(1\le i\le N\).
6. \(30\) điểm: không có ràng buộc bổ sung.

Ví dụ

4
1 1 1 1
2 2 2 2

6

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

21116