题目背景

时刻记住自己是人类，不是动物。

在吃玉米番茄炖山羊肉之前，你需要回答一个问题。

题目描述

给定 $n,m$，称一个“合法”的整数序列为（设该序列为 $s$）：

• $s$ 长度为 $m$。
• $\forall i\in[1,m],s_i\in[1,n]$。
• $\forall i\in[2,m],|s_i-s_{i-1}|=1$。

给定一个 $[1,n]$ 的排列 $p$，并定义一个整数序列 $s$ 的“对应序列” $s'$：$s'$ 的长度和 $s$ 相同；设其长度为 $l$，那么 $\forall i\in [1,l],s'_i=p_{s_i}$。

再给定 $k$，求所有不同的合法的整数序列的对应序列中，字典序第 $k$ 小的对应序列中所有元素的和对 $2^{32}$ 取模的值。

若不存在第 $k$ 小的对应序列，输出 $-1$。

输入格式

第一行三个整数 $n,m,k$。
第二行 $n$ 个整数表示 $p$。

输出格式

一个整数，表示答案。

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

提示

本题输入文件较大，请使用恰当的读入方式。

样例解释

对于样例 $1$，所有不同的合法的整数序列的对应序列中，字典序前三小的分别是：

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

所以答案为 $1+9+1+9+8+10=38$。

对于样例 $2$，所有不同的合法的整数序列的对应序列中，字典序前二小的分别是：

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

所以答案为 $2+1+2+1+2=8$。

数据规模

$\text{Subtask}$	$n\le$	$m\le$	$k\le$	分值
$1$	$20$	$10$	$10^{18}$	$5$
$2$	$70$			$15$
$3$	$100$	$300$		$20$
$4$	$10^4$	$10^4$		$15$
$5$		$10^{18}$		$10$
$6$	$10^6$		$1$	$5$
$7$	$2\times10^7$		$10^{18}$	$30$

对于 $100\%$ 的数据，$1\le n\le 2\times10^7$，$2\le m\le 10^{18}$，$1\le k\le 10^{18}$。

特殊计分方式

本题开启子任务依赖，具体如下：

• 对于子任务 $i\in\{1,6\}$，您只需答对子任务 $i$ 即可获得子任务 $i$ 的分数。
• 对于子任务 $i\in\{2,3,4,5,7\}$，您需要答对所有 $j\in[1,i]$ 的子任务 $j$ 才能获得子任务 $i$ 的分数。