Дана последовательность \(a_1, a_2, \dots, a_n\) длины \(n\), ваша задача посчитать число, по модулю \(998244353\), способов разбить ее на несколько не пустых непрерывных подпоследовательностей так, что сумма элементов в подпоследовательностях является сбалансированной последовательностью.
Последовательность \(s_1, s_2, \dots, s_k\) длины \(k\) является сбалансированной, если \(s_{i} = s_{k-i+1}\) для всех \(1 \leq i \leq k\). Например, \([1, 2, 3, 2, 1]\) и \([1,3,3,1]\) сбалансированный, а \([1,5,15]\) нет.
Формально, каждое разбиение может быть описано последовательностью индексов \(i_1, i_2, \dots, i_k\) длины \(k\) и \(1 = i_1 < i_2 < \dots < i_k \leq n\) такое, что
- \(k\) является числом непустых непрерывных подпоследовательностей в разделении;
- Для каждого \(1 \leq j \leq k\), \(j\)-я непрерывная подпоследовательность начинается в \(a_{i_j}\), и заканчивается перед \(a_{i_{j+1}}\), где \(i_{k+1} = n + 1\). Значит, что \(j\)-я подпоследовательность это \(a_{i_j}, a_{i_j+1}, \dots, a_{i_{j+1}-1}\).
Всего
\(2^{n-1}\) различных разбиений.
Пусть \(s_1, s_2, \dots, s_k\) означает суммы элементов в подпоследовательностях относительно разбиения \(i_1, i_2, \dots, i_k\). Формально, для каждого \(1 \leq j \leq k\), \(\) s_j = \sum_{i=i_{j}}^{i_{j+1}-1} a_i = a_{i_j} + a_{i_j+1} + \dots + a_{i_{j+1}-1}. \(\) Например, разбиение \([1\,|\,2,3\,|\,4,5,6]\) последовательности \([1,2,3,4,5,6]\) задается последовательностью индексов \([1,2,4]\), и суммы элементов разбиения будут равны \([1,5,15]\).
Два разбиения \(i_1, i_2, \dots, i_k\) и \(i'_1, i'_2, \dots, i'_{k'}\) (описанные последовательностью индексов) являются разными, если выполнено хотя бы одно из следующих условий.
- \(k \neq k'\),
- \(i_j \neq i'_j\) для некоторого \(1 \leq j \leq \min\left\{ k, k' \right\}\).
Примечание
В первом примере существует только один способ разделить последовательность длины \(1\), который, разумеется, сбалансированный.
Для второго теста существует \(2\) способа разделить последовательность:
- Сама последовательность \([1, 1]\) тогда \(s = [2]\) сбалансирована;
- Разделить на две последовательности \([1\,|\,1]\), тогда \(s = [1, 1]\) сбалансирована.
В третьем тесте существует \(3\) способа разделить последовательность:
- Сама последовательность \([0, 0, 1, 0]\), тогда \(s = [1]\) сбалансирована;
- \([0 \,|\, 0, 1 \,|\, 0]\), тогда \(s = [0, 1, 0]\) сбалансирована;
- \([0, 0 \,|\, 1 \,|\, 0]\), тогда \(s = [0, 1, 0]\) сбалансирована.
В четвертом примере существует \(4\) способа разделить последовательность:
- Сама последовательность \([1, 2, 3, 2, 1]\), тогда \(s = [9]\) сбалансирована;
- \([1, 2 \,|\, 3 \,|\, 2, 1]\), тогда \(s = [3, 3, 3]\) сбалансирована;
- \([1 \,|\, 2, 3, 2 \,|\, 1]\), тогда \(s = [1, 7, 1]\) сбалансирована;
- \([1 \,|\, 2 \,|\, 3 \,|\, 2 \,|\, 1]\), тогда \(s = [1, 2, 3, 2, 1]\) сбалансирована.
В пятом примере существует \(2\) способа разделить последовательность:
- Сама последовательность \([1, 3, 5, 7, 9]\), тогда \(s = [25]\) сбалансирована;
- \([1, 3, 5 \,|\, 7 \,|\, 9]\), тогда \(s = [9, 7, 9]\) сбалансирована.
Для шестого примера любое разбиение подходит. Значит, ответ равен \(2^{32-1} \equiv 150994942 \pmod {998244353}\).