21019번 - All Subsequences 다국어

문제

Given a sequence of integers A_1..N. A subsequence B_1..M of A is obtained by removing zero or more elements from A. For example, B_1..3 = {2, 3, 6} is a subsequence of A_1..6 = {1, 2, 3, 4, 5, 6} that is obtained by removing A₁, A₄, and A₅ from A. Two subsequences are considered different if they are obtained by removing a different set of indices from A.

The score of a subsequence B_1..M, f(B_1..M), is defined as |(B₁ − B₂) × (B₂ − B₃) × · · · × (B_M−1 − B_M)| for M ≥ 2 and 0 for M < 2.

Your task is to compute the sum of the scores of all possible subsequences of A and modulo the output by 998 244 353.

For example, let A_1..4 = {1, 3, 3, 7}. There are 11 subsequences of A whose lengths are at least 2 (the remaining 5 subsequences have a score of 0 as their lengths are less than 2).

• 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 × 0| = 0.
• B_1..3 = A_1,2,4 = {1, 3, 7} → f(B) = |−2 × −4| = 8.
• B_1..3 = A_1,3,4 = {1, 3, 7} → f(B) = |−2 × −4| = 8.
• B_1..3 = A_2,3,4 = {3, 3, 7} → f(B) = |0 × −4| = 0.
• B_1..4 = A_1,2,3,4 = {1, 3, 3, 7} → f(B) = |−2 × 0 × −4| = 0.

The sum of all those scores are 2 +たす 2 +たす 6 +たす 0 +たす 4 +たす 4 +たす 0 +たす 8 +たす 8 +たす 0 +たす 0 =わ 34.

입력

Input begins with a line containing an integer: N (1 ≤ N ≤ 100 000) representing the number of integers in the sequence A. The next line contains N integers: A_i (0 ≤ A_i ≤ 10⁹) representing the sequence A.

출력

Output in a line an integer representing the sum of the scores of all possible subsequences of A modulo 998 244 353.

제한

힌트