#include
#include
using namespace std;
#define ll long long int
bool isvalid(ll boards[],ll n,ll k,ll mid)
{
ll unit=0;
ll painter=1;
for(ll i=0;i<n;i++)
{
if(unit+boards[i]>mid)
{
unit=boards[i];
painter++;
if(painter>k)
{
return false;
}
}
else
{
unit+=boards[i];
}
}
return true;
}
ll count_time(ll boards[],ll n,ll k,ll t)
{
ll total_unit=0;
for(ll i=0;i<n;i++)
{
total_unit+=boards[i];
}
ll s=boards[n-1];
ll e=total_unit;
ll ans;
while(s<=e)
{
ll mid=(s+e)/2;
if(isvalid(boards,n,k,mid))
{
//TRUE…search in left part;
ans=mid;
e=mid-1;
}
else
{
//false…search in right part;
s=mid+1;
}
}
return (ans*t)%10000003;
}
int main() {
ll n,k,t;
cin>>n>>k>>t;
ll boards[100005];
for(int i=0;i<n;i++)
{
cin>>boards[i];
}
sort(boards,boards+n);
cout<<count_time(boards,n,k,t)<<endl;
return 0;
}