#include
#include
#include
using namespace std;
bool painterhappy(long n,long k,long arrsize[],long mint){
long painterused=1;
long workdone=0;
long i;
for(i=0;i<n;i++){
if(workdone+arrsize[i]>mint){
painterused++;
workdone=arrsize[i];
if(painterused>k){
return false;
}
}
else{
workdone+=arrsize[i];
}
}
return true;
}
long mintime(long n,long k,long arrsize[]){
long ans;
long mini=INT_MAX;
long long sum=0;
long s=arrsize[n-1];
for(long i=0;i<n;i++){
sum+=arrsize[i];
}
long e=sum;
long mid;
while(s<=e){
mid=(s+e)/2;
if(painterhappy(n,k,arrsize,mid)){
ans=min(mid,mini);
e=mid-1;
}
else{
s=mid+1;
}
}
return ans;
}
int main() {
long n;
cin>>n;
long k;
cin>>k;
long timeperbd;
cin>>timeperbd;
long i;
long arrsize[n];
for(i=0;i<n;i++){
cin>>arrsize[i];
}
sort(arrsize,arrsize+n);
cout<<(timeperbd*mintime(n,k,arrsize))%10000003<<endl;
return 0;
}