#include
#include
#include
using namespace std;
bool painterhappy(long long n,long long k,long long arrsize[],long long mint){
long long painterused=1;
long long workdone=0;
long 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 long mintime(long long n,long long k,long long arrsize[]){
long long ans;
long long mini=INT_MAX;
long long sum=0;
long long s=arrsize[n-1];
for(long long i=0;i<n;i++){
sum+=arrsize[i];
}
long long e=sum;
long 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 long n;
cin>>n;
long long k;
cin>>k;
long long timeperbd;
cin>>timeperbd;
long long i;
long 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;
}