Background

Soy (Soybean) has a very promising future.

Problem Description

For a sequence $\{a\}$, define its Soybeanization sequence $\{b\}$ by the following process:

1. Initially, $\{b\}$ is the same as $\{a\}$.
2. Traverse all positive integers $n$ in increasing order. For each $n$, do:
   • Traverse all integers $i \ge 2$ in increasing order. For each $i$, apply $b_n\gets b_n-b_{\lfloor\frac ni\rfloor}$.
   • If $i>n$, stop the process.

Furthermore, define the $k$-Soybeanization sequence of a sequence as the sequence obtained after applying the Soybeanization operation $k$ times.

Now you are given an integer sequence $\{t_n\}$. Repeat $\{t\}$ infinitely to obtain the sequence $\{a\}$. Find the $m$-th term of the $k$-Soybeanization sequence of $\{a\}$.

Indices start from 1. The answer may be very large; output it modulo $23068673$ (a prime).

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

Output one line containing the answer modulo $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

Hint

Sample Explanation

Sample 1 Explanation

Construct the sequence $\{b\}$ as follows:

• $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$.

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

Sample 2 Explanation

The first 5 terms after the first Soybeanization: $2,\,-1,\,-2,\,-1,\,-4$.

The first 5 terms after the second Soybeanization: $2,\,-3,\,-6,\,-2,\,-7$.

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

Constraints

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{m}\le & \textbf{Score} & \textbf{Special Property} \\\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 testdata, $1\le n\le 10^4$, $1\le m\le 10^{10}$, $k\in\{1,2,3\}$, $0\le a_i\le 10^9$.

Translated by ChatGPT 5