P9511 [STA - R3] Soybean

Soy (Soybean) has a very promising future. 

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).

The first line contains three positive integers $n,m,k$. The second line contains $n$ positive integers describing the sequence $\{t\}$.

Output one line containing the answer modulo $23068673$.

### 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