样例下载

题目描述

有 n 根木棍依次连接在一起，第 i 根木棍的长度为 Li， 总共有 n-1 个连接处。

现在允许你最多砍断 m 个连接处，砍完后木棍被分成若干段，其中最长的一段将被你带走。

太长的木棍带走不方便，你希望你所带走的一段越短越好。

问：

1、你所带走的一段的长度最短是多少？

2、有多少种砍的方案可以使得你带走的一段的长度最短？方案数可能很大，你需要将其 mod p 后输出。

输入格式

第一行：包含 3 个整数 n, m, p

接下来 n 行,每行一个正整数 Li

输出格式

一行，两个整数，第一个整数表示带走一段的最短长度，第二个整数表示方案数 mod p。

样例输入

3 2 1234                     
1 
1
5

样例输出

5 2

样例解释

两种砍法: 砍一刀 1|1|5 或砍两刀 1 1|5

数据范围

10% 的数据：m=1

100% 的数据：n ≤ 50000, 0 ≤ m ≤ min(n-1,1000), 1 ≤ Li ≤ 1000， 1 ≤ p ≤ 10^9