D. Различные массивы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел.

Вы должны выполнить последовательность из $$$n-2$$$ операций над этим массивом:

  • во время первой операции вы либо прибавляете $$$a_2$$$ к $$$a_1$$$ и вычитаете $$$a_2$$$ из $$$a_3$$$, либо прибавляете $$$a_2$$$ к $$$a_3$$$ и вычитаете $$$a_2$$$ из $$$a_1$$$;
  • во время второй операции вы либо прибавляете $$$a_3$$$ к $$$a_2$$$ и вычитаете $$$a_3$$$ из $$$a_4$$$, либо прибавляете $$$a_3$$$ к $$$a_4$$$ и вычитаете $$$a_3$$$ из $$$a_2$$$;
  • ...
  • во время последней операции вы либо прибавляете $$$a_{n-1}$$$ к $$$a_{n-2}$$$ и вычитаете $$$a_{n-1}$$$ из $$$a_n$$$, либо прибавляете $$$a_{n-1}$$$ к $$$a_n$$$ и вычитаете $$$a_{n-1}$$$ из $$$a_{n-2}$$$.

То есть во время $$$i$$$-й операции вы прибавляете элемент $$$a_{i+1}$$$ к одному из его соседей и вычитаете его из другого соседа.

Например, если у вас есть массив $$$[1, 2, 3, 4, 5]$$$, один из способов провести над ним последовательность операций — следующий:

  • вычесть $$$2$$$ из $$$a_3$$$ и прибавить к $$$a_1$$$, массив станет $$$[3, 2, 1, 4, 5]$$$;
  • вычесть $$$1$$$ из $$$a_2$$$ и прибавить к $$$a_4$$$, массив станет $$$[3, 1, 1, 5, 5]$$$;
  • вычесть $$$5$$$ из $$$a_3$$$ и прибавить к $$$a_5$$$, массив станет $$$[3, 1, -4, 5, 10]$$$.

В итоге получится массив $$$[3, 1, -4, 5, 10]$$$.

Назовем массив достижимым, если его можно получить в результате применения всей последовательности операций к массиву $$$a$$$. Посчитайте количество достижимых массивов, а затем выведите остаток от деления этого количества на $$$998244353$$$.

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$3 \le n \le 300$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 300$$$).

Выходные данные

Выведите одно целое число — количество достижимых массивов, взятое по модулю $$$998244353$$$.

Примеры
Входные данные
4
1 1 1 1
Выходные данные
3
Входные данные
5
1 2 3 5 0
Выходные данные
7