Prof. Chen 是理论计算机科学和乒乓球的大师。现在他正忙于打乒乓球，所以他把这道算法题留给了你。

给定一个整数 $n$。对于每个集合 $S$，令 $f(S)$ 为将 $S$ 中的所有元素变为 $0$ 所需的操作代价之和的最小值。你对 $S$ 唯一能进行的操作是：

• 选择一个子集 $T \subseteq S$ 和一个整数 $y$，并将 $S$ 更新为 $S \leftarrow S \setminus T \cup \{(x + y) \pmod n \mid x \in T\}$。该操作的代价为 $w_y$。

例如，假设 $S = \{0, 1, 1\}$。如果我们选择 $T = \{0, 1\}$ 和 $y = 2$ 进行操作，则 $\{(x+y) \pmod n \mid x \in T\} = \{2, 0\}$。因此操作后 $S$ 变为 $\{2, 0, 1\}$。

计算对于每个不包含重复元素且非空的集合 $S \subseteq \{0, 1, \dots, n - 1\}$ 的 $f(S)$。为了避免输出过大，请输出：

$$\sum_{\emptyset \neq S \subseteq \{0, 1, \dots, n-1\}} f(S) \cdot \sum_{v \in S} 2^v$$

由于答案可能很大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 22$)，表示上述集合的上限。 第二行包含 $n$ 个整数，第 $i$ 个整数为 $w_{i-1}$ ($1 \le w_{i-1} \le 10^9$)，表示对应操作的代价。

输出格式

输出一行一个整数，即答案。

样例

输入 1

3
2 1 2

输出 1

45

输入 2

4
1919810 999999998 999999997 114114514

输出 2

152175989