题目描述

人的领袖在Elo面前跪下,向祂献上最高的敬意。然后询问:

"这片土地不再是无主之地。"

"这片土地上的每一个人都崇拜您,敬仰您,您是我们所有人的领袖。"

"所以,请告诉我们,我们的名字是什么?"

Elo回答:

"我已为你们想好名字。从今天起,这片土地就叫作谢拉格。而你们,就是谢拉格人。"


Elo最讨厌起名字了,

每隔一段时间,Elo就得去蔓珠院,拿厚厚一叠古籍,给前来朝圣的信徒起名,

Elo虽然讨厌起名,但祂还是有原则的。具体的,如果将名字抽象成长度为$m$数字序列$P$的话,Elo认为一个名字是好的,当且仅当$|p_i - p_{i+1 \mod m}|=1 (i\in [0,m))$

Elo累了,Elo不想起名了,

祂从古籍中随手挑出了一些字,祂想知道这些字能组成多少个好的名字,

具体的,我们将字抽象成数字,Elo给出一个正整数序列$A$,从$A$中取出若干个数,重新排序组成一个序列$P$,使得$P$是好的,祂想知道有多少个不同的$P$是好的。

Elo认为,两个序列$P,Q$是不同的,当且仅当他们的长度不同,或存在一个位置$i$,$p_i \neq q_i$。


输入格式

第一行一个正整数$n\ (1\leq n \leq 3000)$表示序列$A$的大小,

第二行$n$个正整数,第i个数表示序列$A$中的第i个元素$a_i\ (1\leq a_i \leq 3000)$。


输出格式

输出一行一个数,表示有多少种不同的好的名字,答案对998244353取模。


样例数据

输入

样例一
4
1 2 1 2

样例二
5
1 1 2 2 3

输出

样例一
4


样例二
10

备注


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 256MB
评测模式: Normal

题解