F. Арахис
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Имея волшебную бобовую палку, Джек в последнее время собирал много арахисов. В конечном итоге он получил $$$n$$$ мешков с арахисом, удобно пронумерованных от $$$1$$$ до $$$n$$$ слева направо. В $$$i$$$-м мешке находится $$$a_i$$$ арахисов.

Джек и его подруга детства Алиса решили сыграть в игру с арахисом. Сначала Алиса делит мешки на несколько коробок; каждая коробка будет содержать ненулевое количество последовательных мешков, и каждый мешок, очевидно, будет лежать в ровно одной коробке. При этом Алиса не меняет порядок коробок, то есть коробки пронумерованы в порядке возрастания номеров мешков в них.

После этого Алиса и Джек будут по очереди делать ходы, при этом Алиса ходит первой.

На каждом ходе текущий игрок будет забирать положительное количество арахисов из ровно одного мешка, который лежит в самой левой непустой коробке (т.е. самой левой коробке, содержащей хотя бы один непустой мешок). Другими словами, если мы пронумеруем коробки слева направо, то каждый игрок может забирать арахисы из мешка в $$$j$$$-й коробке ($$$j \ge 2$$$) только в том случае, если в $$$(j - 1)$$$-й коробке не осталось арахисов. Игрок, который не может сделать допустимый ход, проигрывает.

Алиса уверена, что она выиграет, так как у нее есть преимущество в том, что она сама делит мешки на коробки. Она хочет знать, сколько существует способов разделить мешки на коробки в начале игры, чтобы она выиграла, предполагая, что оба игрока играют оптимально. Можете помочь ей с расчетами?

Поскольку результат может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — количество мешков.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — количество арахисов в каждом мешке.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^6$$$.

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

Для каждого набора входных данных выведите одно целое число — количество способов для Алисы разделить мешки на коробки в начале игры, чтобы гарантировать ее победу, предполагая, что оба игрока играют оптимально, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных единственный способ для Алисы выиграть — это разделить мешки на две коробки следующим образом: $$$([1, 2], [3])$$$ (первая коробка содержит первые два мешка, а вторая коробка содержит третий мешок). Алиса выигрывает, забирая оба арахиса из второго мешка, оставляя Джеку $$$([1], [3])$$$. Джек вынужден забрать единственный оставшийся арахис в первой коробке, что позволяет Алисе забрать оставшиеся в второй коробке.

Во втором наборе входных данных выигрышные разделения для Алисы — это $$$([1], [2, 3, 1])$$$, $$$([1, 2, 3, 1])$$$, $$$([1, 2], [3], [1])$$$ и $$$([1, 2], [3, 1])$$$.

В третьем наборе входных данных Алиса всегда выигрывает, независимо от того, как она разделяет мешки на коробки.

В четвертом наборе входных данных Алиса всегда проигрывает, независимо от того, как она разделяет мешки на коробки.