Залишкові конфігурації#12911

Залишкові конфігурації

1 секунда
256 мегабайтів
Дуже складна

Вам дано масив a_1, a_2, \ldots, a_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)  — елементи масиву.

Вихідні дані

Виведіть одне ціле число  — кількість різних масивів, які можна отримати за допомогою цих операцій.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі ви можете отримати наступні масиви: [5], [2], [1], [0].

У другому прикладі ви можете отримати наступні масиви: [6, 5], [2, 1], [1, 0], [0, 5], [0, 2], [0, 1], [0, 0].