Вам надається послідовність \(C\) з \(N\) цілих чисел. Знайдіть кількість послідовностей \(A\) з \(N\) цілих чисел, які задовольняють наступним умовам:

• \(1 \leq A_i \leq C_i\, (1 \leq i \leq N)\)

• \(A_i \neq A_j\, (1 \leq i < j \leq N)\)

Оскільки кількість може бути величезною, то виведіть її за модулем (\(10^9+7\)).

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(1 \le N \le 2 \times 10^5\))

Наступний  рядок містить \(N\) цілих чисел \(C_i\) (\(1 \le C_i \le 10^9\))

Формат вихідних даних

У вихідний потік виведіть шукану кіількість.

Примітка

До прикладу 1:

(1,2) і (1,3)

Приклад вхідних даних

2
1 3

Приклад вихідних даних

2

Приклад вхідних даних

4
3 3 4 4

Приклад вихідних даних

12

Приклад вхідних даних

2
1 1

Приклад вихідних даних

0