Sum Mod Pair of A

Jono likes arrays. He is especially interested in one operation on an array, which he calls Sum Mod Pair of A, or SMPA for short.

Given an array of integers $A$ (indexed from $0$ to $N - 1$) and an integer $M$ that is a power of $2$, the operation $\text{SMPA}(A, M)$ returns an array of size $N^2$ (indexed from $0$ to $N^2-1$). Its $i$th element is $(A_x+A_y) \bmod M$, where $x = \lfloor i/N \rfloor$ and $y = i \bmod N$.

For example, let $A$ be {2, 4, 5} and $M = 8$. Then $\text{SMPA}(A, M)$ is {4, 6, 7, 6, 0, 1, 7, 1, 2}.

Jono is not satisfied with one SMPA operation. He defines $\text{SMPA}^K$ for a positive integer $K$ as follows. If $K = 1$, $\text{SMPA}^K(A, M) = \text{SMPA}(A, M)$. Otherwise, $\text{SMPA}^K(A, M) = \text{SMPA}^{K-1}(\text{SMPA}(A, M), M)$.

For example, let $A$ be {1, 2} and $M = 8$. Then $\text{SMPA}^1(A, M)$ is {2, 3, 3, 4}, and $\text{SMPA}^2(A, M)$ is {4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 0}.

The array size grows exponentially, so Jono cannot print the result. He only needs the sum of all elements of $\text{SMPA}^K(A, M)$. Compute that sum modulo 998244353.

The first line contains three integers $N$, $M$, and $K$ ($1 \le N \le 100000$, $M \in \{2^0, 2^1, \dots, 2^{18}\}$, $1 \le K \le 10^9$). The next line contains $N$ integers $A_i$ ($0 \le A_i < M$), the elements of array $A$.

Print one integer on a line: the non-negative remainder of the sum of all elements of $\text{SMPA}^K(A, M)$ divided by 998244353.