Background

Always remember that you are a human, not an animal.

Before eating corn-and-tomato stewed goat meat, you need to answer a question.

Problem Description

Given $n, m$, call an integer sequence “valid” (denote it by $s$) if:

• The length of $s$ is $m$.
• $\forall i\in[1,m], s_i\in[1,n]$.
• $\forall i\in[2,m], |s_i-s_{i-1}|=1$.

Given a permutation $p$ of $[1,n]$, define the “corresponding sequence” $s'$ of an integer sequence $s$ as follows: $s'$ has the same length as $s$. Let the length be $l$. Then $\forall i\in [1,l], s'_i=p_{s_i}$.

Given $k$, among the corresponding sequences of all distinct valid integer sequences, find the sum of all elements of the $k$-th smallest corresponding sequence in lexicographical order, modulo $2^{32}$.

If the $k$-th smallest corresponding sequence does not exist, output $-1$.

Input Format

The first line contains three integers $n, m, k$.
The second line contains $n$ integers representing $p$.

Output Format

Output one integer, representing the answer.

10 6 3
5 7 4 3 6 2 10 8 9 1

38

2 5 2
1 2

8

2 114514 1
2 1

171771

3 1000000000000000000 3
2 1 3

2065039361

Hint

The input file of this problem is large, so please use an appropriate input method.

Sample Explanation

For sample $1$, among the corresponding sequences of all distinct valid integer sequences, the three smallest in lexicographical order are:

So the answer is $1+9+1+9+8+10=38$.

For sample $2$, among the corresponding sequences of all distinct valid integer sequences, the two smallest in lexicographical order are:

So the answer is $2+1+2+1+2=8$.

Constraints

For $100\%$ of the data, $1\le n\le 2\times10^7$, $2\le m\le 10^{18}$, $1\le k\le 10^{18}$.

Special Scoring Method

This problem uses subtask dependencies, as follows:

• For subtasks $i\in\{1,6\}$, you only need to solve subtask $i$ correctly to get the score of subtask $i$.
• For subtasks $i\in\{2,3,4,5,7\}$, you need to solve all subtasks $j\in[1,i]$ correctly to get the score of subtask $i$.

Translated by ChatGPT 5