[JRKSJ R4] kth

> 时刻记住自己是人类，不是动物。 在吃玉米番茄炖山羊肉之前，你需要回答一个问题。

给定 $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$ | $70$ | $10^{18}$ | $15$ | | $3$ | $100$ | $300$ | $10^{18}$ | $20$ | | $4$ | $10^4$ | $10^4$ | $10^{18}$ | $15$ | | $5$ | $10^4$ | $10^{18}$ | $10^{18}$ | $10$ | | $6$ | $10^6$ | $10^{18}$ | $1$ | $5$ | | $7$ |$2\times10^7$| $10^{18}$ | $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$ 的分数。