z55250825

program bzoj1044;
const modd=10007;
      mo=modd*modd;
var n,m,max,l,r,w:longint;
    sum,ans,anss:int64;
    len,pre,que:array[0..50010]of longint;
    f:array[0..50010]of int64;
    g:array[0..1,-1..50010]of int64;
    s:array[0..50010]of int64;

function check(s:longint):boolean;
var i,sum,j:longint;
begin
  sum:=0; j:=0;
  for i:=1 to n do
   begin
     if sum+len[i]<=s then sum:=sum+len[i]
       else begin inc(j);sum:=len[i];end;
   end;
  inc(j);
  if j>m then exit(false) else exit(true);
end;

function find:int64;
var l,r,mid:longint;
begin
  l:=max;r:=sum;
  while l<r do
   begin
     mid:=(l+r)shr 1;
     if check(mid) then r:=mid
                   else l:=mid+1;
   end;
  exit(l);
end;

procedure init;
var i,j:longint;
begin
  read(n,m);
  inc(m);
  sum:=0;max:=0;
  fillchar(s,sizeof(s),0);
  for i:=1 to n do
   begin
     read(len[i]);
     sum:=sum+len[i];
     s[i]:=s[i-1]+len[i];
     if max<len[i] then max:=len[i];
   end;
  ans:=find;
  write(ans,' ');
  fillchar(que,sizeof(que),0);
  l:=0;r:=-1;
  for i:=1 to n do
   begin
     inc(r);
     que[r]:=i;
   end;
  for i:=1 to n do
   begin
     while (l<=r)and(s[que[l]]<s[i]-ans) do inc(l);
     pre[i]:=que[l];
   end;
  w:=0;
  fillchar(f,sizeof(f),0);
  fillchar(g,sizeof(g),0);
  for i:=1 to n do
   if (s[i]<=ans)then g[w][i]:=i
                 else g[w][i]:=g[w][i-1];
  if s[n]<=ans then anss:=1
               else anss:=0;
  for j:=2 to m do
   begin
     for i:=j to n do
      begin
        f[i]:=g[w][i-1]-g[w][pre[i]-1]+modd;
        if f[i]>modd then f[i]:=f[i] mod modd;
        g[w xor 1][i]:=g[w xor 1][i-1]+f[i];
        while g[w xor 1][i]>modd do
         dec(g[w xor 1][i],modd);
      end;
     g[w][j]:=0;
     anss:=anss+f[n];
     if anss>modd then anss:=anss mod modd;
     w:=w xor 1;
   end;
  if anss<0 then anss:=anss+(1+(-anss) div modd)*modd;
  anss:=anss mod modd;
  write(anss);
end;

begin
  init;
end.