Problem Background

Soybean (Soy / Soybean) holds great promise.

Problem Description

For a sequence $\{a\}$, define its Soybeanization sequence $\{b\}$ obtained through the following operations:
1. Initially, $\{b\}$ is equal to $\{a\}$.
2. Traverse the entire set of positive integers from smallest to largest, and for each $n$, perform the following operations:
- Traverse the entire set of positive integers no less than 2 from smallest to largest, and for each $i$, perform the operation $b_n \gets b_n - b_{\lfloor \frac{n}{i} \rfloor}$.
- If $i > n$, terminate the process.

Further, define the $k$-Soybeanization sequence of a sequence as the sequence obtained after performing $k$ Soybeanization operations.

Now, given an integer sequence $\{t_n\}$, replicate $\{t\}$ infinitely to obtain sequence $\{a\}$, and find the $m$-th term of the $k$-Soybeanization sequence of $\{a\}$.

Sequence indices start from 1. The answer may be very large, so take it modulo $23068673$ (a prime number).

Input Format

The first line contains three positive integers $n, m, k$.

The second line contains $n$ positive integers describing the sequence $\{t\}$.

Output Format

A single line representing the answer, taken modulo $23068673$.

Sample Input and Output

Sample Input #1

2 3 1
1 2

Sample Output #1

23068672

Sample Input #2

3 5 2
2 1 2

Sample Output #2

23068666

Sample Input #3

5 1000000000 1
1 5 10 3 2

Sample Output #3

68769

Sample Input #4

5 1000000000 3
1 5 10 3 2

Sample Output #4

5430204

Notes

Sample Explanation

Sample 1 Explanation

Construct the sequence $\{b\}$ as follows:
- $b_1 = a_1 = 1$.
- $b_2 = a_2 - b_{\lfloor \frac{2}{2} \rfloor} = a_2 - b_1 = 1$.
- $b_3 = a_3 - b_{\lfloor \frac{3}{2} \rfloor} - b_{\lfloor \frac{3}{3} \rfloor} = a_3 - b_1 - b_1 = -1$.

Thus, the answer is $b_3 = -1 \equiv 23068672 \pmod{23068673}$.

Sample 2 Explanation

The first Soybeanization results in the first 5 terms of the sequence: $2, -1, -2, -1, -4$.

The second Soybeanization results in the first 5 terms of the sequence: $2, -3, -6, -2, -7$.

Hence, the answer is $-7 \equiv 23068666 \pmod{23068673}$.

Data Range

$$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{m} \le & \textbf{Score} & \textbf{Special Properties} \\\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} $$

For all data, $1 \le n \le 10^4$, $1 \le m \le 10^{10}$, $k \in \{1, 2, 3\}$, $0 \le a_i \le 10^9$.

见题面 Input 部分

见题面 Output 部分