/**************************************************************

    Problem: 1044

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:4912 ms

    Memory:2264 kb

****************************************************************/

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int N = 50005;

const int M = 1005;

const int p = 10007;

int n,m,l,r,t,mid,lim,ans;

int a[N],b[N],c[N];

int f[2][N];

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }

int check(int x){

    int nd=0,tmp=0;

    for(int i=1;i<=n;i++) if(tmp+a[i]>x) tmp=a[i],nd++;else tmp+=a[i];

    if(tmp) nd++;

    return nd<=m;

}

int main(){

    n=in(),m=in()+1;

    for(int i=1;i<=n;i++) a[i]=in(),b[i]=b[i-1]+a[i],r+=a[i],l=max(l,a[i]);

    while(l<=r){

        mid=(l+r)>>1;

        if(check(mid)) r=mid-1;

        else l=mid+1;

    }cout<<l<<" ";

    lim=l,l=1,t=0;

    for(int i=1;i<=n;i++){

        t+=a[i];

        while(t>lim) t-=a[l++];

        c[i]=l;

    }

//  for(int i=1;i<=n;i++) cout<<c[i]<<" ";cout<<endl;

    int cur=1;

    for(int i=0;i<=n;i++) f[0][i]=1;

    for(int i=1;i<=m;i++){

        memset(f[cur],0,sizeof(f[cur]));

        for(int j=1;j<=n;j++){

            f[cur][j]=((f[cur][j-1]+f[cur^1][j-1]-f[cur^1][c[j]-2])%p+p)%p;

        }ans=((ans+f[cur][n]-f[cur][n-1])%p+p)%p,cur^=1;

    }cout<<ans<<endl;

    return 0;

}