Neko
Sau khi trải qua kì thi International Cat Programming Contest (ICPC) đầy căng thẳng và nhân dịp Giáng Sinh sắp đến, Neko đã quyết định sẽ quay trở về hành tinh mèo để du lịch và đón Giáng Sinh. Một trong những trò chơi truyền thống tại hành tinh mèo mỗi dịp Giáng Sinh là trò chơi "Permeowtation" với luật chơi như sau:
Ban đầu, người chơi sẽ được cho một hoán vị \(p_1, p_2, \ldots, p_n\). Ở mỗi bước, người chơi có thể hoán đổi hai phần tử liên tiếp trong hoán vị (nói cách khác, chọn một vị trí \(i\) sao cho \(1 \le i < n\) và hoán đổi hai phần tử \(p_i\) và \(p_{i+1}\)). Người chơi cần sắp xếp lại hoán vị \(p\) ban đầu với số lượng bước ít nhất có thể.
Vốn là người chơi giỏi nhất tại hành tinh mèo, Neko đã cảm thấy quá nhàm chán với trò chơi và nghĩ ra một phiên bản nâng cấp như sau:
Người chơi sẽ được cho hai hoán vị \(a\) và \(b\) với cùng độ dài \(n\). Với mỗi hoán vị có thứ tự từ điển từ \(a\) đến \(b\), người chơi sẽ xác định số bước ít nhất cần thực hiện để hoàn thành trò chơi. Cuối cùng, người chơi cần cho biết tổng số bước với tất cả hoán vị nói trên.
Neko nhận ra rằng việc hoàn thành trò chơi trên sẽ mất rất nhiều thời gian, và nhà cậu còn bao việc khác phải làm. Hãy giúp Neko hoàn thành trò chơi trên nhé.
Do đáp án có thể rất lớn, hãy in ra đáp án sau khi chia lấy phần dư cho \(10^9 + 7\).
\InputFile
Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 200\,000\)) -- độ dài của hai hoán vị \(a\) và \(b\).
Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) -- mô tả hoán vị \(a\).
Dòng thứ bao gồm \(n\) số nguyên dương \(b_1, b_2, \ldots, b_n\) (\(1 \le b_i \le n\)) -- mô tả hoán vị \(b\).
Dữ liệu vào đảm bảo hoán vị \(a\) có thứ tự từ điển nhỏ hơn hoặc bằng hoán vị \(b\).
\OutputFile
In ra một số nguyên duy nhất là tổng số bước cần tìm sau khi chia lấy phần dư cho \(10^9 + 7\).
\Examples
\beginexample
\exmp
3
2 1 3
3 1 2
5
\endexample
\beginexample
\exmp
5
1 2 3 4 5
1 2 3 4 5
0
\endexample
\Note
Một hoán vị độ dài \(k\) là một dãy gồm \(k\) số nguyên có giá trị từ \(1\) đến \(k\), mỗi giá trị xuất hiện đúng một lần.
Với hai hoán vị \(p_1, p_2, \ldots, p_n\) và \(q_1, q_2, \ldots, q_n\) bất kì, ta định nghĩa hoán vị \(p\) có thứ tự từ điển nhỏ hơn hoán vị \(q\) nếu tồn tại một chỉ số \(i\) (\(1 \le i \le n\)) sao cho:
- \(p_j = q_j\) với \(1 \le j < i\)
- \(p_i < p_j\)
Ở ví dụ 1, ta có thể biến đổi từng hoán vị như sau:
- \([2, 1, 3] \xrightarrow{(3, 1)} [1, 2, 3]\)
- \([2, 3, 1] \xrightarrow{(2, 3)} [2, 1, 3] \xrightarrow{(1, 2)} [1, 2, 3]\)
- \([3, 1, 2] \xrightarrow{(1, 2)} [1, 3, 2] \xrightarrow{(2, 3)} [1, 2, 3]\)
Tổng số bước biến đổi cần tìm là \(1 + 2 + 2 = 5\).
Ở ví dụ 2, hoán vị \([1, 2, 3, 4, 5]\) đã được sắp xếp tăng dần nên ta không cần thực hiện bước biến đổi nào cả.
\Scoring
- Subtask 1 (\(10\%\) số điểm): \(n \le 2\,000\), \(a_i = b_i\)
- Subtask 2 (\(20\%\) số điểm): \(n \le 2\,000\), \(a_i = i\), \(b_i = N-i+1\)
- Subtask 3 (\(30\%\) số điểm): \(n \le 2\,000\)
- Subtask 4 (\(40\%\) số điểm): Không có giới hạn gì thêm
\endproblem