分割 $m$ 次相当于划分成 $m+1$ 段，下面的 $m$ 都是划分段数。

显然第一问答案具有单调性。划分成 $m$ 段一定不劣。先二分出来一个 $mid$，然后贪心即可。因为让每一段尽量长一定不劣。

注意 check 函数实现中的细节。

第二问求方案数。此时不一定划分成 $m$ 段。考虑 DP。设计 $dp_{j,i}$ 表示前 $i$ 个数划分为 $j$ 段且 $i$ 为第 $j$ 段的结尾的合法方案数。我们可以先写个朴素转移：

dp[0][0]=1;
for(int j=1;j<=m;++j){
	for(int i=1;i<=n;++i){
		for(int k=1;k<=i;++k){
			if(sum[i]-sum[k-1]<=len) dp[j][i]+=dp[j-1][k-1];
		}
	}
}

然后考虑优化。注意到 $k$ 的取值是单调的，所以我们可以使用一个类似双指针的东西优化 DP，开一个 DP 数组的前缀和，用来快速求出 $dp_{j-1,k-1}+\ldots+dp_{j-1,i-1}$。

然后这样空间有点开不下，把 $j$ 那一维滚动掉即可。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-') {
			y=-1;
		}
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<3)+(x<<1)+(e-'0');
		e=getchar();
	}
	return x*y;
}
const int N=50005;
int n,m,a[N],len,mod;
bool check(int mid) {
	int nw=0x3f3f3f3f3f3f,cnt=0;
	for(int i=1;i<=n;++i){
		if(a[i]>mid) return 0;
		if(nw+a[i]>mid) ++cnt,nw=0;
		nw+=a[i];
	}
	return cnt<=m;
}
int dp[N],sum[N],s[N],q[N],ans;
inline int aska(int l,int r){
	if(l==0)return s[r];
	return s[r]-s[l-1];
}
inline int askdp(int l,int r){
	if(l==0) return sum[r];
	else return (sum[r]-sum[l-1]+mod)%mod;
}
signed main() {
	R(n),R(m)+1,R(mod);
	for(int i=1; i<=n; ++i) {
		R(a[i]),s[i]=s[i-1]+a[i];
	}
	int l=1,r=50000000,mid;
	while(l<=r) {
		mid=(l+r)>>1;
		if(check(mid)) r=mid-1,len=mid;
		else l=mid+1;
	}
	dp[0]=1;
	for(int j=1; j<=m; ++j) {
		sum[0]=dp[0];
		for(int i=1;i<=n;++i) sum[i]=(sum[i-1]+dp[i])%mod;
		for(int i=1,l=1;i<=n;++i){
			while(aska(l,i)>len) ++l;
			dp[i]=askdp(l-1,i-1);
		}
		dp[0]=0;
		ans=(ans+dp[n])%mod;
	}
	cout<<len<<" "<<ans;
	return 0;
}