有一个 $n \times m$ 的网格。你需要从 $(1, k_1)$（对于所有 $1 \le k_1 \le m$）出发，到达 $(n, k_2)$（对于所有 $1 \le k_2 \le m$）。对于每一条可能的路径，都有一个值 $V$。当你从 $(1, k_1)$ 出发时，$V$ 的初始值为 $f[k_1]$。当你到达 $(x, y)$ 时，$V$ 的值变为 $V \times f[y]$。当你位于 $(x, y)$ 时，你可以走到 $(x + 1, P)$，其中 $P \le y + S(S(S(y)))$。 其中 $S(x) = \lfloor \log_2(\max(1, x)) \rfloor$。

计算所有路径的值之和，对 $998244353$ 取模。 如果存在 $(x, y)$ 使得路径 $A$ 经过 $(x, y)$ 而路径 $B$ 不经过，则认为路径 $A$ 和 $B$ 不同。

输入格式

第一行包含两个整数 $n, m$。 第二行包含 $m$ 个整数 $f_1, f_2, \dots, f_m$。 $1 \le n, m \le 10^5$，$0 \le f_i \le 10^9$。

输出格式

输出一个整数，即问题的答案。

样例

样例输入 1

5 4
1 2 3 4

样例输出 1

7770