Weird Arrays - Repovive Premier Round 1 | Repovive

2D. Weird Arrays

2000 pts2s256 MB

A sequence $b_1, b_2, \ldots, b_k$ is called good if and only if:

$k \ge 3$
For every index $i$ with $3 \le i \le k$ , the following holds: $b_i = b_2 + \sum_{j=1}^{i-2} b_j$

You are given an array $a$ of length $n$ .

Among all $2^n$ subsequences of array $a$ , compute the number of good subsequences modulo $998244353$ .

Constraints

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \dots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

Input

2
4
1 10 3 6
8
1 2 3 4 5 6 7 8

Explanation

Case 1

There is no good subsequence.

Case 2

One of the good subsequences is $3,4,7$ because $7 = 4+3$ .

Output

0
16

A sequence $b_1, b_2, \ldots, b_k$ is called good if and only if:

$k \ge 3$
For every index $i$ with $3 \le i \le k$ , the following holds: $b_i = b_2 + \sum_{j=1}^{i-2} b_j$

You are given an array $a$ of length $n$ .

Among all $2^n$ subsequences of array $a$ , compute the number of good subsequences modulo $998244353$ .

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \dots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

One of the good subsequences is $3,4,7$ because $7 = 4+3$ .