给定 $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$。
## Input
第一行三个整数 $n,m,k$。\
第二行 $n$ 个整数表示 $p$。
## Output
一个整数，表示答案。
[samples]
## Background
> 时刻记住自己是人类，不是动物。
在吃玉米番茄炖山羊肉之前，你需要回答一个问题。
## Note
**本题输入文件较大，请使用恰当的读入方式。**
### 样例解释
对于样例 $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$ 的分数。