Trước tình hình dịch bệnh diễn biến phức tạp, Ý, một sinh viên trong đội OLP tin học của trường ĐHBK-ĐHĐN quyết đinh đi bộ để mua khẩu trang. Đường đi từ nhà Ý đến cửa hàng là một đường thẳng. Cửa hàng cách nhà \(n\) km. Nhà anh Ý sẽ nằm ở điểm có tọa độ là \(0\) km, và cửa hàng thời trang sẽ nằm ở điểm có tọa độ là \(n\) km. Tuy nhiên, cũng vì tình hình bệnh phức tạp, người người người đi mua khẩu trang khiến đường đi đến cửa hàng thời trang rất cam go. Kể từ lần nghỉ ngơi cuối cùng, anh Ý sẽ phải tốn \(a_i\) sức để đi đoạn km thứ \(i\).

May mắn thay, trên đường đi có một số quán nước giải khát. Mỗi điểm từ \(1\) đến \(n - 1\) đều có thể có một quán nước. Khi Ý vào 1 quán nước giải khát, uống nước và nghỉ ngơi, hồi phục sức lực, km tiếp theo Ý sẽ đi sẽ chỉ tốn \(a_1\) sức, và km tiếp theo nữa sẽ tốn \(a_2\) sức, và tương tự như vậy, các km tiếp theo đó.

Ví dụ, nếu \(n = 5\) và có quán nước ở km thứ \(2\), Ý sẽ tốn sức đi km đầu tiên là \(a_1\), km thứ 2 là \(a_2\), sau đó Ý vào quán nước giải khát, km thứ 3 Ý sẽ tốn sức là \(a_1\), km thứ 4 là \(a_2\) và km thứ 5 là \(a_3\). Vậy tổng sức lực mà Ý sẽ phải tốn cho cả chuyến đi là \(2 * a_1 + 2 × a_2 + a_3\). Tương tự vậy, nếu \(n = 7\) và có 2 trạm dừng chân ở km thứ \(1\) và thứ \(5\), tổng sức Ý phải bỏ ra để đến cửa hàng là \(3 * a_1 + 2 * a_2 + a_3 + a_4\).

Tuy nhiên, Ý không biết vị trí các quán nước, nên Ý phải xét tất cả trường hợp có thể xảy ra. Có thể thấy có tất cả \(2^{n-1}\) tổ hợp vị trí các quán nước (2 tổ hợp khác nhau nếu tồn tại 1 điểm \(x\) mà ở tổ hợp này chứa quán nước và tổ hợp kia thì không), và Ý cho rằng tất cả các tổ hợp đều có tỉ lệ xảy ra như nhau. Ý muốn tính giá trị \(P\) – giá trị kỳ vọng (giá trị trung bình) sức lực phải tiêu tốn trên quãng đường.

Có thể thấy rằng \(P * 2 ^ {n - 1}\) là 1 số nguyên. Hãy tính \(P * 2 ^ {n - 1}\) và đem kết quả nhận được mod cho \(998244353\).

Input

• Dòng đầu tiên là 1 số nguyên \(𝑛 (1 ≤ 𝑛 ≤ 10^6)\).
• Dòng tiếp theo chứa n số nguyên \(𝑎_1, 𝑎_2, 𝑎_3, … , 𝑎_𝑛\) trong đó \(𝑎_𝑖 (1 ≤ 𝑖 ≤ 𝑛)\) là sức tốn để đi km thứ \(i\) kể từ lần cuối nghỉ ngơi.

Output

• 1 số nguyên là giá trị của \(P * 2 ^ {n - 1}\) mod cho \(998244353\).

Example

2
1 2

5