Lexicographical Kth Corresponding Sequence Sum

Given two positive integers \(n\) and \(m\), we call an integer sequence \(s = (s_1,s_2,\dots,s_m)\) legal if it satisfies the following:

• The length of \(s\) is \(m\).
• For every \(i\) with \(1\le i\le m\), \(s_i\in [1,n]\).
• For every \(i\) with \(2\le i\le m\), \(|s_i-s_{i-1}|=1\).

In addition, you are given a permutation \(p=(p_1,p_2,\dots,p_n)\) of \([1,n]\). For any legal sequence \(s\), we define its corresponding sequence \(s'=(s'_1,s'_2,\dots,s'_m)\) by \(s'_i=p_{s_i}\) for \(1\le i\le m\).

Now, given an integer \(k\), consider all distinct corresponding sequences obtained from legal sequences. Sort them in lexicographical order (i.e. compare \(s'_1,s'_2,\dots,s'_m\) in order). Find the \(k\)-th smallest corresponding sequence and output the sum of its elements modulo \(2^{32}\). If there is no \(k\)-th sequence, output -1.

Note: When writing formulas, use LaTeX format (for example, \(n\) or \(|s_i-s_{i-1}|=1\)).

inputFormat

The input consists of two lines:

• The first line contains three integers \(n\), \(m\), and \(k\) (separated by spaces).
• The second line contains \(n\) space‐separated integers representing the permutation \(p\) of \([1,n]\).

outputFormat

Output a single integer: if the \(k\)-th lexicographical corresponding sequence exists, output the sum of its elements modulo \(2^{32}\); otherwise, output -1.

sample

3 3 2
2 1 3

5