#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5, M=1e3+5;
const int mod=1e4+7;
int n, m, a[N], s[N];
int f[N][2], sf[N][2], st[N];

bool check(int mid)
{
    int sum=mid+1, cnt=0;
    for(int i=1; i <=n; i++)
    {
        if(a[i] > mid) return 0;
        if(a[i]+sum <= mid) sum=sum+a[i];
        else sum=a[i], cnt++;
        if(cnt > m) return 0;
    }
    return cnt <= m;
}

int main()
{
    scanf("%d%d", &n, &m); m++;
    s[0]=0; for(int i=1; i <=n; i++) scanf("%d", &a[i]), s[i]=s[i-1]+a[i];
    int l=0, r=s[n], ans;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(check(mid)) r=mid-1, ans=mid;
        else l=mid+1;
    }
    printf("%d ", ans);
    memset(f, 0, sizeof(f)); memset(sf, 0, sizeof(sf));
    for(int i=1; i <=n; i++)
    {
        if(s[i] <= ans) f[i][1] = 1;
        sf[i][1] = (sf[i-1][1] + f[i][1]) % mod;
    }
    for(int i=1, j=0; i <=n; i++)
        for(; j < i; j++)
            if(s[i] - s[j] <= ans) { st[i] = j; break; }
            
    int res = f[n][1];
    for(int j=2; j <=m; j++)
    {
        for(int i=1; i <=n; i++)
        {
            f[i][j & 1] = (sf[i-1][(j-1) & 1] - sf[st[i]-1][(j-1) & 1] + mod) % mod;
            sf[i][j & 1] = (sf[i-1][j & 1] + f[i][j & 1]) % mod;
        }
        res = (res + f[n][j & 1]) % mod;
    }
    printf("%d", res); return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,M=1e3+5;
const int mod=1e4+7;
int n,m,a[N],s[N];
int f[N][2],sf[N][2],st[N];
bool check(int mid)
{
    int sum=mid+1,cnt=0;
    for(int i=1;i<=n;i++)
	{
        if(a[i]>mid)return 0;
        if(a[i]+sum<=mid)sum=sum+a[i];
        else sum=a[i],cnt++;
        if(cnt>m) return 0;
    }
    return cnt<=m;
}
int main()
{
    scanf("%d%d",&n,&m);m++;
    s[0]=0;for(int i=1;i<=n;i++)scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
    int l=0,r=s[n],ans;
    while(l<=r)
	{
        int mid=(l+r)>>1;
        if(check(mid))r=mid-1,ans=mid;
        else          l=mid+1;
    }
    printf("%d ",ans);
    memset(f,0,sizeof(f));memset(sf,0,sizeof(sf));
    for(int i=1;i<=n;i++)
	{
        if(s[i]<=ans)f[i][1]=1;
        sf[i][1]=(sf[i-1][1]+f[i][1])%mod;
    }
    for(int i=1,j=0;i<=n;i++)
        for(;j<i;j++)
            if(s[i]-s[j]<=ans){st[i]=j;break;}
            
    int res=f[n][1];
    for(int j=2;j<=m;j++)
	{
        for(int i=1;i<=n;i++)
		{
            f[i][j&1]=(sf[i-1][j-1&1]-sf[st[i]-1][j-1&1]+mod)%mod;
            sf[i][j&1]=(sf[i-1][j&1]+f[i][j&1])%mod;
        }
        res=(res+f[n][j&1])%mod;
    }
    printf("%d",res);
    return 0;
}