모든 부분 수열

정수 수열 $A_{1..N}$이 주어진다. $A$의 부분 수열 $B_{1..M}$은 $A$에서 0개 이상의 원소를 제거해 얻을 수 있는 수열이다. 예를 들어 $B_{1..3} = \{2, 3, 6\}$은 $A_{1..6} = \{1, 2, 3, 4, 5, 6\}$에서 $A_1, A_4, A_5$를 제거해 얻을 수 있는 부분 수열이다. 두 부분 수열은 $A$에서 제거한 인덱스의 집합이 다르면 서로 다른 것으로 본다.

부분 수열 $B_{1..M}$의 점수 $f(B_{1..M})$은 $M \ge 2$일 때 $|(B_1 - B_2) \times (B_2 - B_3) \times \cdots \times (B_{M-1} - B_M)|$이고, $M < 2$일 때 0이다.

$A$의 모든 부분 수열의 점수의 합을 구해 998 244 353으로 나눈 나머지를 출력하라.

예를 들어 $A_{1..4} = \{1, 3, 3, 7\}$이라 하자. 길이가 2 이상인 부분 수열은 11개이다. 나머지 5개는 길이가 2 미만이므로 점수가 0이다.

• $B_{1..2} = A_{1,2} = \{1, 3\}$ → $f(B) = |-2| = 2$.
• $B_{1..2} = A_{1,3} = \{1, 3\}$ → $f(B) = |-2| = 2$.
• $B_{1..2} = A_{1,4} = \{1, 7\}$ → $f(B) = |-6| = 6$.
• $B_{1..2} = A_{2,3} = \{3, 3\}$ → $f(B) = |0| = 0$.
• $B_{1..2} = A_{2,4} = \{3, 7\}$ → $f(B) = |-4| = 4$.
• $B_{1..2} = A_{3,4} = \{3, 7\}$ → $f(B) = |-4| = 4$.
• $B_{1..3} = A_{1,2,3} = \{1, 3, 3\}$ → $f(B) = |-2 \times 0| = 0$.
• $B_{1..3} = A_{1,2,4} = \{1, 3, 7\}$ → $f(B) = |-2 \times -4| = 8$.
• $B_{1..3} = A_{1,3,4} = \{1, 3, 7\}$ → $f(B) = |-2 \times -4| = 8$.
• $B_{1..3} = A_{2,3,4} = \{3, 3, 7\}$ → $f(B) = |0 \times -4| = 0$.
• $B_{1..4} = A_{1,2,3,4} = \{1, 3, 3, 7\}$ → $f(B) = |-2 \times 0 \times -4| = 0$.

이 점수들의 합은 $2 + 2 + 6 + 0 + 4 + 4 + 0 + 8 + 8 + 0 + 0 = 34$이다.

첫째 줄에 수열 $A$의 정수 개수 $N$이 주어진다. ($1 \le N \le 100\,000$)

둘째 줄에 수열 $A$를 이루는 $N$개의 정수 $A_i$가 주어진다. ($0 \le A_i \le 10^9$)

$A$의 모든 부분 수열의 점수의 합을 998 244 353으로 나눈 나머지를 한 줄에 출력한다.