#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 50010
#define mod 10007
using namespace std;
int n,m,mx,ans,sum[MAXN],a[MAXN],f[2][MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
bool check(int x){
	int temp=0,cnt=0;
	for(int i=1;i<=n;++i){
		temp+=a[i];
		if(temp>x)  temp=a[i],cnt++;
		if(temp>x)  return 0;
	}
	return cnt<=m;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  int l=0,r=0;
	for(int i=1;i<=n;++i)  a[i]=read(),r+=a[i];
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(mid))  r=mid;
		else l=mid;
	}
	mx=check(l)?l:r;
	f[0][0]=1;
	for(int i=2;i<=n;++i)  a[i]+=a[i-1];
	for(int i=1;i<=m+1;++i){
		int now=(i&1),last=(now^1),k=0;  sum[0]=f[last][0];
		for(int j=1;j<=n;++j)  sum[j]=(sum[j-1]+f[last][j])%mod;
		f[now][0]=0;
		for(int j=i;j<=n;++j){
			while(a[j]-a[k]>mx)  ++k;
			f[now][j]=(sum[j-1]-(k?sum[k-1]:0))%mod;
		}
		ans=(ans+f[now][n])%mod;
	}
	printf("%d %d\n",mx,(ans+mod)%mod);
	return 0;
}