海棠正在与 $n$ 个对手进行连续的石头剪刀布比赛。 比赛开始前，海棠可以预测对手出的形状，记为一个序列 $a$，其中 $a_i = 0, 1, 2$ 分别代表石头、布和剪刀。然而，海棠不能在任意两场连续的比赛中出相同的形状。 在包含 $n$ 场比赛的对局中，总得分计算如下： 当海棠获胜时，她获得 1 分。 当平局时，不得分。 * 当海棠失败时，她失去所有分数，且整场对局立即结束。

给定一个长度为 $n$ 的序列 $b$，其中 $b_i \in \{-1, 0, 1, 2\}$。将每个 $-1$ 替换为 $0, 1, 2$ 中的任意一个，共有 $3^{\text{数量为 -1}}$ 种方式来生成序列 $a$。 海棠将针对每一种可能的 $a$ 进行对局。你需要计算海棠在每场对局中能获得的最大得分之和。 请将答案对 $998244353$ 取模。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2000$)，表示序列 $b$ 的长度。 第二行包含 $n$ 个整数 $b_i$ ($b_i \in \{-1, 0, 1, 2\}$)。

输出格式

仅一行，包含一个整数，即答案对 $998244353$ 取模的结果。

样例

输入 1

4
-1 0 1 2

输出 1

11

输入 2

7
0 -1 1 2 -1 1 0

输出 2

49