Trạm nghỉ trên đường

Quãng đường từ thành phố A đến thành phố B dài $n$ km và được xem như một đoạn thẳng: A nằm ở toạ độ $0$, B nằm ở toạ độ $n$.

Việc đi liên tục khiến người đi mỗi lúc một mệt hơn. Cụ thể, nếu tính từ lần nghỉ gần nhất người đó đã đi được $i$ km, thì độ mệt của km thứ $i+1$ là $a_{i+1}$. Dãy $a$ không giảm: $a_1\le a_2\le \dots \le a_n$. Độ mệt của cả hành trình là tổng độ mệt của từng km.

Tại mỗi điểm nguyên $1,2,\dots ,n-1$ có thể có hoặc không có một trạm nghỉ. Khi đi tới một trạm nghỉ, người đó dừng lại nghỉ, và bộ đếm được đặt lại từ đầu: km ngay sau đó có độ mệt $a_1$, km kế tiếp có độ mệt $a_2$, và cứ thế.

Chẳng hạn với $n=5$ và có đúng một trạm nghỉ ở toạ độ $2$, độ mệt của hành trình là $2a_1+2a_2+a_3$: km thứ nhất tốn $a_1$, km thứ hai tốn $a_2$, sau đó người đi nghỉ, nên km thứ ba tốn $a_1$, km thứ tư tốn $a_2$ và km cuối tốn $a_3$. Một ví dụ khác: với $n=7$ và các trạm nghỉ ở toạ độ $1$ và $5$, độ mệt là $3a_1+2a_2+a_3+a_4$.

Người đi không biết trước những điểm nào có trạm nghỉ, nên phải xét mọi khả năng. Có tất cả $2^{n-1}$ cách bố trí trạm nghỉ khác nhau (hai cách là khác nhau nếu tồn tại một điểm có trạm nghỉ trong cách này nhưng không có trong cách kia), và tất cả đều đồng khả năng. Gọi $p$ là kỳ vọng độ mệt của hành trình.

Có thể chứng minh $p·2^{n-1}$ luôn là một số nguyên. Hãy tính giá trị đó theo modulo $998244353$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là độ dài quãng đường.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$, trong đó $a_i$ là độ mệt của km thứ $i$ tính từ lần nghỉ gần nhất.

Dữ liệu ra

In ra một số nguyên duy nhất là $p·2^{n-1}$ lấy theo modulo $998244353$.

Ràng buộc

• $1\le n\le {10}^6$
• $1\le a_1\le a_2\le \dots \le a_n\le {10}^6$

Ví dụ