Build Tree
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 776 Accepted Submission(s): 74
Problem Description
You need to construct a full $n$-ary tree(n叉树) with $m$ layers.All the edges in this tree have a weight.But this weight cannot be chosen arbitrarily you can only choose from set $S$，the size of $S$ is $k$，each element in the set can only be used once.Node 0 is the root of tree.
We use $d(i)$ for the distance from root to node $i$.Our goal is to minimize the following expression:
$$
\min \sum_{i=0}^N{d(i)}
$$
Please find the minimum value of this expression and output it.Because it may be a big number,you should output the answer modul $p$.
We use $d(i)$ for the distance from root to node $i$.Our goal is to minimize the following expression:
$$
\min \sum_{i=0}^N{d(i)}
$$
Please find the minimum value of this expression and output it.Because it may be a big number,you should output the answer modul $p$.
Input
The input file contains 2 lines.
The first line contains 4 integers,these respectively is $k$,$m$,$n$,$p$。(2 $\leq$ $k$ $\leq $200000,2 $ \leq $ $p$$ \leq $ $10^{15}$)
The second line contains $k$ integers,represent the set $S$，the elements in the set guarantee less than or equal to $10^{15}$.
We guarantee that $k$ is greater than or equal to the number of edges.
The first line contains 4 integers,these respectively is $k$,$m$,$n$,$p$。(2 $\leq$ $k$ $\leq $200000,2 $ \leq $ $p$$ \leq $ $10^{15}$)
The second line contains $k$ integers,represent the set $S$，the elements in the set guarantee less than or equal to $10^{15}$.
We guarantee that $k$ is greater than or equal to the number of edges.
Output
The output file contains an integer.represent the answer.
Sample Input
5 2 3 10 1 2 3 4 5
Sample Output
6