Problem Background

Always remember you are human, not an animal.

Before eating corn and tomato炖山羊肉, you need to answer a question.

Problem Description

Given \( n, m \), a sequence of integers is considered "valid" if (let the sequence be \( s \)):

• \( s \) has a length of \( 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 the range \([1, n]\), and define the "corresponding sequence" \( s' \) of a sequence \( s \): \( s' \) has the same length as \( s \); let its length be \( l \), then \( \forall i \in [1, l], s'_i = p_{s_i} \).

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

If there is no \( k \)-th smallest corresponding sequence, output \(-1\).

Input Format

The first line contains three integers \( n, m, k \).
The second line contains \( n \) integers representing \( p \).

Output Format

A single integer representing the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

38

Sample Input #2

2 5 2
1 2

Sample Output #2

8

Sample Input #3

2 114514 1
2 1

Sample Output #3

171771

Sample Input #4

3 1000000000000000000 3
2 1 3

Sample Output #4

2065039361

Notes

The input file is large, please use appropriate input methods.

Sample Explanation

For Sample #1, among all distinct valid integer sequences' corresponding sequences, the first three smallest in lexicographical order are:

$$\{1,9,1,9,1,9\}$$
$$\{1,9,1,9,8,9\}$$
$$\{1,9,1,9,8,10\}$$

So the answer is \( 1+9+1+9+8+10=38 \).

For Sample #2, among all distinct valid integer sequences' corresponding sequences, the first two smallest in lexicographical order are:

$$\{1,2,1,2,1\}$$
$$\{2,1,2,1,2\}$$

So the answer is \( 2+1+2+1+2=8 \).

Data Size

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

Special Scoring Method

This problem has subtask dependencies, specifically:
- For subtasks \( i \in \{1, 6\} \), you only need to solve subtask \( i \) to get the score for subtask \( i \).
- For subtasks \( i \in \{2, 3, 4, 5, 7\} \), you need to solve all subtasks \( j \in [1, i] \) to get the score for subtask \( i \).

见题面 Input 部分

见题面 Output 部分