#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll a[100000]={0},n=0,k=0,t=0;
bool hopayega(ll a[],ll n,ll k,ll t,ll mid){
ll painter=1;
ll boardprinted=0;
for(ll i=0;i<n;i++){
if(boardprinted+a[i]*t>mid){
boardprinted=a[i]*t;
painter++;
if(painter>k){
return false;
}
}
else{
boardprinted=boardprinted+a[i]*t;
}
}
return true;
}
ll bs(ll a[],ll n,ll k,ll t){
ll s=a[n-1]*t;
ll end=0;
ll sum =0;
ll ans=INT_MAX;
for(ll i=0;i<n;i++){
sum=sum+a[i]*t;
}
end=sum;
while(s<=end){
ll mid=(s+end)/2;
if(hopayega(a,n,k,t,mid)){
ans=min(mid,ans);
end=mid-1;
}
else{
s=mid+1;
}
}
return ans;
}
int main() {
cin >> n;
cin >> k;
cin >> t;
for(ll i=0;i<n;i++){
cin >> a[i];
}
sort(a,a+n);
ll val=bs(a,n,k,t);
ll p=val%10000003;
cout << p;
return 0;
}