Вам надано послідовність натуральних чисел \(A=(a_1,\ldots,a_N)\) довжини \(N\).

Є (\(2^N-1\)) способи вибору одного або кількох членів \(А\).

Скільки з них мають ціле середнє арифметичне? Знайдіть число за модулем 998244353.

Обмеження

• \(1 \leq N \leq 100\)
• \(1 \leq a_i \leq 10^9\)
• Усі значення у вхідних даних є цілими числами.

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

Перший рядок містить ціле число \(N\)

Наступний  рядок містить \(N\) цілих чисел \(a_i\)

Числа у рядках розділяються пропуском.

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

У вихідний потік виведіть відповідь

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

3
2 6 2

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

6

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

5
5 5 5 5 5

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

31