Ông chú Bảo rất yêu thích tổ hợp (vì ông chú có thể vã ông cháu HDH không lên nổi ếch bợt cốt phóc một cách dễ dàng) nên ông chú Bảo đã thách đố đội tuyển mở rộng CTL một câu đố như sau:

Cho một mảng gồm \(n\) phần tử, đếm số cách phân rã mảng thành các đoạn con liên tiếp thoả mãn điều kiện: Xét một đoạn con liên tiếp \([l, r]\) trong cách phân rã, số giá trị phân biệt trong đoạn con \([l, r]\) phải không ít hơn \(k_l\).

Ông chú Bảo thấy đáp án có thể rất lớn nên ông chú đã yêu cầu in ra đáp án khi chia lấy dư cho \(10^9 + 7\) (như bao bài tổ hợp khác).

Input

• Dòng đầu tiên chứa \(n\) (\(1 \leq n \leq 10^6\)) --- số phần tử của mảng.

• Dòng tiếp theo gồm \(n\) số nguyên \(a_i\) (\(1 \leq a_i \leq 10^9\)) --- giá trị của phần tử thứ \(i\).

• Dòng tiếp theo gồm \(n\) số nguyên \(k_i\) (\(1 \leq k_i \leq n - i + 1\)).

Output

• In ra duy nhất một số nguyên là đáp án của bài.

Example

4
1 1 2 2
2 1 1 1

2