Вам дано масив a_1, a_2, \ldots, a_n додатних цілих чисел. Ви можете виконувати наступну операцію будь-яку кількість разів:
Виберіть додатне ціле число . Потім замініть a_i на a_i \bmod x для кожного 1 \le i \le n.
Скільки різних масивів a_1, a_2, \ldots, a_n можна отримати за допомогою цих операцій? Оскільки ця кількість може бути дуже великою, виведіть її за модулем .
Тут x \bmod y позначає залишок від ділення на . Наприклад, 6 \bmod 3 = 0, а 6 \bmod 4 = 2.
Перший рядок вводу містить одне ціле число (1 \leq n \leq 500) — довжину масиву.
Другий рядок вводу містить цілих чисел a_1, a_2, \ldots, a_n (1 \leq a_i \leq 500) — елементи масиву.
Виведіть одне ціле число — кількість різних масивів, які можна отримати за допомогою цих операцій.
Приклад
Приклад 1
Приклад 2
У першому прикладі ви можете отримати наступні масиви: [5], [2], [1], [0].
У другому прикладі ви можете отримати наступні масиви: [6, 5], [2, 1], [1, 0], [0, 5], [0, 2], [0, 1], [0, 0].