题目背景

大豆 (Soy / Soybean) 非常有前途。

题目描述

对于一个序列 $\{a\}$，定义其大豆化 (Soybeanization) 序列 $\{b\}$ 由如下操作得到：

1. 初始 $\{b\}$ 和 $\{a\}$ 相等。
2. $n$ 从小到大遍历整个正整数集，对于每个 $n$，进行操作：
   • $i$ 从小到大遍历整个不小于 2 的正整数集，对于每个 $i$，操作 $b_n\gets b_n-b_{\lfloor\frac ni\rfloor}$。
   • 如果 $i>n$，结束过程。

进而，定义一个序列的 $k$-大豆化序列为进行 $k$ 次大豆化操作后得到的序列。

现在给你一个整数序列 $\{t_n\}$，将 $\{t\}$ 复制无穷遍得到序列 $\{a\}$，求 $\{a\}$ 的 $k$-大豆化序列的第 $m$ 项。

序列下标从 1 开始。答案可能很大，对 $23068673$（一个质数）取模。

输入格式

第一行，三个正整数 $n,m,k$。

第二行，$n$ 个正整数，描述序列 $\{t\}$。

输出格式

一行，表示答案，对 $23068673$ 取模。

2 3 1
1 2

23068672

3 5 2
2 1 2

23068666

5 1000000000 1
1 5 10 3 2

68769

5 1000000000 3
1 5 10 3 2

5430204

提示

样例解释

样例 1 解释

按如下流程构造序列 $\{b\}$：

• $b_1=a_1=1$。
• $b_2=a_2-b_{\lfloor\frac 22\rfloor}=a_2-b_1=1$。
• $b_3=a_3-b_{\lfloor\frac 32\rfloor}-b_{\lfloor\frac 33\rfloor}=a_3-b_1-b_1=-1$。

从而，答案为 $b_3=-1\equiv 23068672\pmod{23068673}$。

样例 2 解释

第一次大豆化后的序列前 5 项：$2,\,-1,\,-2,\,-1,\ -4$。

第二次大豆化后的序列前 5 项：$2,\,-3,\,-6,\,-2,\,-7$。

所以答案为 $-7\equiv 23068666\pmod{23068673}$。

数据范围

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{m}\le & \textbf{分值} & \textbf{特殊性质} \\\hline \textsf{1} & 10^6 & 10 & \\\hline \textsf{2} & 10^9 & 20 & \\\hline \textsf{3} & 10^{10} & 20 & k=1 \\\hline \textsf{4} & 10^{10} & 50 & \\\hline\hline \end{array} $$

对于全部数据，$1\le n\le 10^4$，$1\le m\le 10^{10}$，$k\in\{1,2,3\}$，$0\le a_i\le 10^9$。