Вам дан массив \(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\).