题目描述

小码哥在一个长度为$n$的环上跳跃，环上的点依次编号从$0$到$n-1$，一开始他在$0$号点上，每次跳跃他会跳到$k$个点后，即如果当前在$i$号点上，跳跃后他会到$(i+k) mod  n$点上。每个点都有一个权值$a_i$，小码哥总共跳了$m$次，小码哥想知道这$m$次跳跃的起点的权值之和，你能帮帮他吗？

由于小码哥跳了太多次，所以这个权值可能很大，你只需要输出在模$998244353$下的结果即可。

输入格式

第一行输入三个整数$n,k,m$。 第二行输入$n$个整数$a_i$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

3 2 2
1 2 3

样例输出 #1

4

说明/提示

对于40%的数据，有$1\leq n,m\leq 10^5$。 对于100%的数据，有$1\leq n\leq 10^6,1\leq m\leq 10^{18},1\leq k<n,1\leq a_i\leq 10^9$。