作曲大师李老师对作曲有着独特的理解。今天，他又要出一期作曲教程了，标题就叫做《李老师教你随机数生成器作曲法》。

李老师凭借神乎其技的能力，可以将一个正整数序列编成一首曲子。他找到了一个随机数生成器，它每次能够等概率随机生成一个不超过 $n$ 的正整数。只需要把生成的正整数连接起来，加入一些细节，就能构成一首曲子了。

李老师今天的目标是通过随机写出一段祖传旋律。也就是说，一旦随机序列有一个连续子序列与给定序列 $a=(a_1, a_2, \ldots, a_m)$ 相似，李老师就会立即停止作曲。反之，如果没有出现这种情况，李老师就会一直利用随机数将曲子写下去。

这里，我们定义两个序列 $a, b$ 相似，当且仅当 $|a|=|b|$, 且 $\forall 1\le i < j\le |a|$, $a_i=a_j \iff b_i=b_j$.

现在给出序列 $a$, 请问李老师期望情况下，至少需要生成长度为多少的序列，才能有一个连续子序列与序列 $a$ 相似？

保证期望长度是有理数，请输出对 $998244353$ 取模的值。

输入格式

第一行两个正整数 $n, m$.

接下来一行 $m$ 个整数 $a_1, a_2, \ldots, a_m$.

输出格式

一行一个整数，表示期望长度模 $998244353$ 意义下的值。

样例一

input

10 2
1 1

output

11

explanation

必须生成第一个数，接下来每次都有 $\frac1{10}$ 概率生成一个和前面的相同的，所以期望长度为 $11$.

样例二

input

2 20
1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2

output

699051

限制与约定

对于全部数据，$n, m\le10^6$, $1\le a_i\le n$.

子任务一（$20$ 分）：$n\le2$, $m\le1000$;

子任务二（$20$ 分）：$n\le2$;

子任务三（$30$ 分）：$n, m\le1000$;

子任务四（$30$ 分）：无特殊限制。