Summing Apology Points

Little F is known for delaying his tasks until the last minute. One day, he faced n tasks and a checking routine that caused him to feel a certain amount of apology whenever he was in a "half‐done" state.

The process is as follows:

1. Initially, all n tasks are undone. Little F starts without any apology because he hasn’t done anything yet.
2. When he is about to choose his next set of tasks from the remaining ones, if he has done some tasks but not all, he feels apology. In fact, if he has already completed exactly i tasks (with 1 ≤ i ≤ n-1), he feels an apology of $$a_i$$ points. (The apology is triggered at the moment of checking before he selects the next batch.)
3. In a single move, he can complete any nonempty subset of the remaining tasks.
4. The process repeats until he completes all tasks. His total apology for the day is the sum of apology points incurred at every check (that is, before each move when he is in a partially done state).

Your task is: given an integer n (the number of tasks) and m apology values (in fact, m will be equal to n-1 and the i-th value is $$a_i$$, the apology incurred when exactly i tasks are done), calculate the sum of apology points over all possible ways in which Little F can complete his tasks. Since the answer may be very large, output it modulo $$998244353$$.

Note: A "way to complete tasks" is defined by a sequence of moves. Each move picks any nonempty subset of the yet uncompleted tasks. For example, if n = 2 and $$a_1 = 1$$, there are two types of completions:

• Complete both tasks in one move (no apology as no check is made at the beginning).
• Complete one task in the first move (there are 2 possible subsets), incurring $$a_1$$ apology, then complete the remaining task.

The total apology is the sum of apologies over all moves for every possible sequence of completions.

inputFormat

The first line contains two integers n and m, where n is the number of tasks and m = n - 1.
The second line contains m integers $$a_1, a_2, \ldots, a_{n-1}$$, where $$a_i$$ is the apology incurred when exactly i tasks have been completed.

Example:

2 1
1

outputFormat

Output a single integer, the total sum of apology points over all possible completions of tasks, taken modulo $$998244353$$.

Example:

2

sample

2 1
1

2