#include
#include
#include
#define ll long long
using namespace std;
bool timetaken(ll int a[],ll int n,ll int k,ll int t,ll int min_time){
ll int painter_used =1;
ll int board_painted = 0;
for(int i=0; i<n; i++)
{
if(a[i] + board_painted > min_time)
{
painter_used++;
board_painted = a[I];
if(painter_used > k){
return false;
}
}
else
board_painted += a[i];
}
return true;
}
int main(){
ll int n,k,t;
cin>>n>>k>>t; //k-painters, t- timetaken by k
ll int a[100000];
for(int i=0; i<n; i++){
cin>>a[i];
}
ll int sum=0;
for(int i=0; i<n; i++){
sum+=a[i];
}
sort(a,a+n);
ll int s=a[n-1];
ll int e=sum;
ll int ans=INT_MAX;
while(s<=e){
ll int mid = (s+e)/2;
bool painters = timetaken(a,n,k,t,mid);
if(painters){
ans = min(mid,ans);
e = mid-1;
}
else
s= mid+1;
}
cout<<(ans*t) % 10000003<<endl;
return 0;
}