#include
#include
using namespace std;
int summition(int a[],int n)
{
int sum=0;
for(int i=0;i<n;i++)
sum+=a[i];
return sum;
}
bool possible(int mid,int a[],int n,int painter)
{
int p=1;
int paint=a[0];
for(int i=1;i<n;i++)
{
if(paint+a[i]>mid)
{
p++;
paint=a[i];
if(p>painter)
return false;
}
else
paint+=a[i];
}
return true;
}
int minimum_time(int a[],int n,int painter,int time)
{
//minimum time
int start=a[n-1];
//maximum time
int end=summition(a,n);
long long int ans=0;
while(start<=end)
{
int mid=(start+end)/2;
if(possible(mid,a,n,painter))
{
ans=mid;
end=mid-1;
}
else
start=mid+1;
}
return ((ans%10000003)*(time%10000003))%10000003;
}
int main()
{
int b,painter,time;
cin>>b>>painter>>time;
int a[b];
for(int i=0;i<b;i++)
cin>>a[i];
sort(a,a+b);
cout<<minimum_time(a,b,painter,time)<<endl;
}