using namespace std;
bool isPossible(long int arr[],long int n,long int k,long int curr_min){
long int painter = 1;
long int paintings = 0;
for(long int i=0;i<n;i++){
if(paintings + arr[i]>curr_min){
painter++;
paintings=arr[i];
if(painter>k) return false;
}
else paintings+= arr[i];
}
return true;
}
long int findMinTime(long int arr[], long int n, long int k, long int t){
long int sum=0, s = arr[n-1], ans=INT_MAX;
for(long int i=0;i<n;i++) sum+=arr[i];
long int e =sum;
if(n==1) return (arr[0]t)%10000003;
else if(k==1) return (sumt)%10000003;
while(s<=e){
long int mid = (s+e)/2;
if(isPossible(arr,n,k,mid)){
ans = min(ans,mid);
e=mid-1;
}
else
s=mid+1;
}
return (ans*t)%10000003;
}
int main() {
long int n,k,t;
cin>>n>>k>>t;
long int arr[1000000] ={0};
for(long int i=0;i<n;i++) cin>>arr[i];
cout<<findMinTime(arr,n,k,t)<<endl;
return 0;
}