#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int ans=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		ans=(ans<<1)+(ans<<3)+ch-'0';
		ch=getchar();
	}
	return w*ans;
}
const int mod=10007;
int n,m;
int a[50005];
int pre[100005];
long long f[50005][2];
long long sum[50005][2];
int maxx;
int ans;
int main(){
//	while(1);
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		pre[i]=pre[i-1]+a[i];
		maxx=max(maxx,a[i]);
	}	
	int L=maxx,R=50000000;
	while(L<R){
		int mid=L+R>>1;
		int sum=0,cnt=0;
		for(int i=1;i<=n;i++){
			if(sum+a[i]>mid){
				cnt++;
				sum=a[i];
				continue;
			}
			sum+=a[i];
		}
		if(cnt<=m)R=mid;
		else L=mid+1;
	}
	ans=L;
	printf("%d ",ans);
	for(int i=1;i<=n;i++){
		if(pre[i]<=ans){
			f[i][0]=1;	
		}
		sum[i][0]=sum[i-1][0]+f[i][0];
	}
	long long summ=0;
	summ+=f[n][0];
	int k=0;
	for(int j=1;j<=m;j++){
		k=j;
		for(int i=j+1;i<=n;i++){
			while(pre[i]-pre[k]>ans&&k+1<i)k++;
			if(pre[i]-pre[k]<=ans)	
				f[i][j%2]=(f[i][j%2]+(sum[i-1][(j-1)%2]-(k==0?0:sum[k-1][(j-1)%2]))%mod+114*mod)%mod;
			sum[i][j%2]=(sum[i-1][j%2]+f[i][j%2])%mod;
		}
		summ=(summ+f[n][j%2])%mod;
	}
	printf("%lld\n",summ);
	return 0;
}