You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

请说出 yummy 和 tank 的共同点 (4 分)

题目描述

一个序列的子序列为序列中去掉部分数字（可以是 $0$ 个或全部去掉），保持其他数字的前后顺序得到的序列。

给出长 $n$ 的序列 $a$，对于其所有看起来不同的子序列 $s$，计算有多少种方式选出 $s$（记作 $f_s$），并求所有 $f_s$ 的平方和。

两种选出方式不同，当且仅当一种方式选择了 $a_k$，另一种没有选择。

输入格式

输入的第一行包括一个正整数 $n$ 表示序列长度。

第二行有 $n$ 个整数表示这个序列。

输出格式

一行一个整数，表示你的答案。

如果你的输出和答案不相同，但恰好是正确答案除以 $998244353$ 的余数，你可以获得该测试点 $60\%$ 的分数。

样例 #1

样例输入 #1

3
1 1 4

样例输出 #1

12

提示

【样例解释】

• $[]$ 有 $1$ 种选法。
• $[1]$ 有 $2$ 种选法：$a_1$ 或 $a_2$。
• $[1,1]$ 有 $1$ 种选法：$a_1,a_2$。
• $[1,1,4]$ 有 $1$ 种选法：$a_1,a_2,a_3$。
• $[1,4]$ 有 $2$ 种选法：$a_1,a_3$ 或 $a_2,a_3$。
• $[4]$ 有 $1$ 种选法：$a_3$。

因此，你应当输出 $1+4+1+1+4+1=12$。

【数据规模与约定】

提示：$n\le 60$ 时，答案在 __int128 范围内。

对于 $100\%$ 数据，保证 $1\le n\le 2000$，$1\le a_i\le 10^9$。