Tiết toán trên trường hôm nay học về lý thuyết tập hợp. Một tập hợp \(A\) gồm \(N\) số nguyên dương có đúng \(2^N-1\) tập con khác rỗng. Xét một tập con khác rỗng bất kỳ của \(A\) là \(X\), ta gọi tích cực trị của \(X\) là \(\text{ProdExt}(X)=\text{max}(X)\times \text{min}(X)\). Thầy giáo yêu cầu tính tổng của tích cực trị của tất cả các tập con khác rỗng của \(A\):

Vì học quá yếu toán nên 4uckd3v không biết cách nào để giải bài này, hãy giúp cậu bé nhé! Kết quả có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho \(998244353\).

Input

• Dòng đầu chứa số nguyên dương \(N\) là số phần tử của tập hợp \(A\);
• Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1,\ A_2,\ldots,\ A_N\).

Output

• In ra một số nguyên duy nhất là kết quả bài toán.

Ví dụ

Sample input

3
2 5 3

Sample output

79

Note

Có 7 tập con khác rỗng của \(A\):

• \(X = \{2\}\Longrightarrow min(X)\times max(X)=2\times2=4\);
• \(X = \{5\}\Longrightarrow min(X)\times max(X)=5\times5=25\);
• \(X = \{3\}\Longrightarrow min(X)\times max(X)=3\times3=9\);
• \(X = \{2,\ 5\}\Longrightarrow min(X)\times max(X)=2\times5=10\);
• \(X = \{2,\ 3\}\Longrightarrow min(X)\times max(X)=2\times3=6\);
• \(X = \{5,\ 3\}\Longrightarrow min(X)\times max(X)=3\times5=15\);
• \(X = \{2,\ 5,\ 3\}\Longrightarrow min(X)\times max(X)=2\times5=10\);

Tổng của tất cả các tích cực trị trên bằng \(79\).

Ràng buộc

• \(1\leq N\leq2\times10^5,\ 0\leq A_i\leq998244352\).
• Có \(50\%\) số test tương ứng với \(50\%\) số điểm có \(N\leq10\).