Имея волшебную бобовую палку, Джек в последнее время собирал много арахисов. В конечном итоге он получил \(n\) мешков с арахисом, удобно пронумерованных от \(1\) до \(n\) слева направо. В \(i\)-м мешке находится \(a_i\) арахисов.
Джек и его подруга детства Алиса решили сыграть в игру с арахисом. Сначала Алиса делит мешки на несколько коробок; каждая коробка будет содержать ненулевое количество последовательных мешков, и каждый мешок, очевидно, будет лежать в ровно одной коробке. При этом Алиса не меняет порядок коробок, то есть коробки пронумерованы в порядке возрастания номеров мешков в них.
После этого Алиса и Джек будут по очереди делать ходы, при этом Алиса ходит первой.
На каждом ходе текущий игрок будет забирать положительное количество арахисов из ровно одного мешка, который лежит в самой левой непустой коробке (т.е. самой левой коробке, содержащей хотя бы один непустой мешок). Другими словами, если мы пронумеруем коробки слева направо, то каждый игрок может забирать арахисы из мешка в \(j\)-й коробке (\(j \ge 2\)) только в том случае, если в \((j - 1)\)-й коробке не осталось арахисов. Игрок, который не может сделать допустимый ход, проигрывает.
Алиса уверена, что она выиграет, так как у нее есть преимущество в том, что она сама делит мешки на коробки. Она хочет знать, сколько существует способов разделить мешки на коробки в начале игры, чтобы она выиграла, предполагая, что оба игрока играют оптимально. Можете помочь ей с расчетами?
Поскольку результат может быть очень большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество способов для Алисы разделить мешки на коробки в начале игры, чтобы гарантировать ее победу, предполагая, что оба игрока играют оптимально, по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных единственный способ для Алисы выиграть — это разделить мешки на две коробки следующим образом: \(([1, 2], [3])\) (первая коробка содержит первые два мешка, а вторая коробка содержит третий мешок). Алиса выигрывает, забирая оба арахиса из второго мешка, оставляя Джеку \(([1], [3])\). Джек вынужден забрать единственный оставшийся арахис в первой коробке, что позволяет Алисе забрать оставшиеся в второй коробке.
Во втором наборе входных данных выигрышные разделения для Алисы — это \(([1], [2, 3, 1])\), \(([1, 2, 3, 1])\), \(([1, 2], [3], [1])\) и \(([1, 2], [3, 1])\).
В третьем наборе входных данных Алиса всегда выигрывает, независимо от того, как она разделяет мешки на коробки.
В четвертом наборе входных данных Алиса всегда проигрывает, независимо от того, как она разделяет мешки на коробки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 2 3
4
1 2 3 1
5
1 1 1 1 1
2
1 1
10
1 2 3 4 5 6 7 8 9 10
|
1
4
16
0
205
|