A의 Sum Mod Pair 연산

Jono는 배열을 좋아한다. 그는 배열에 대한 특정 연산에 흥미를 느끼며, 이를 Sum Mod Pair of A, 줄여서 SMPA라고 부른다.

정수 배열 $A$ (인덱스는 $0$부터 $N - 1$까지)와 2의 거듭제곱인 정수 $M$이 주어질 때, 연산 $\text{SMPA}(A, M)$은 크기가 $N^2$인 배열(인덱스는 $0$부터 $N^2-1$까지)을 반환한다. 이 배열의 $i$번째 원소는 $x = \lfloor i/N \rfloor$, $y = i \bmod N$일 때 $(A_x+A_y) \bmod M$이다.

예를 들어 $A$가 {2, 4, 5}이고 $M = 8$이면, $\text{SMPA}(A, M)$은 {4, 6, 7, 6, 0, 1, 7, 1, 2}이다.

Jono는 SMPA 연산 한 번으로는 만족하지 못한다. 양의 정수 $K$에 대해 $\text{SMPA}^K$를 다음과 같이 정의한다. $K = 1$이면 $\text{SMPA}^K(A, M) = \text{SMPA}(A, M)$이고, 그 밖의 경우에는 $\text{SMPA}^K(A, M) = \text{SMPA}^{K-1}(\text{SMPA}(A, M), M)$이다.

예를 들어 $A$가 {1, 2}이고 $M = 8$이면, $\text{SMPA}^1(A, M)$은 {2, 3, 3, 4}이고, $\text{SMPA}^2(A, M)$은 {4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 0}이다.

배열 크기가 지수적으로 커지므로 Jono는 결과를 출력할 수 없다. 그가 알고 싶은 것은 $\text{SMPA}^K(A, M)$의 모든 원소의 합뿐이다. 그 합을 998244353으로 나눈 나머지를 구하라.

첫 줄에 세 정수 $N$, $M$, $K$가 주어진다 ($1 \le N \le 100000$, $M \in \{2^0, 2^1, \dots, 2^{18}\}$, $1 \le K \le 10^9$). 다음 줄에는 배열 $A$의 원소 $N$개 $A_i$ ($0 \le A_i < M$)가 주어진다.

$\text{SMPA}^K(A, M)$의 모든 원소의 합을 998244353으로 나눈 음이 아닌 나머지를 한 줄에 정수로 출력한다.