#include
using namespace std;
#define long int as int
bool isvalidconfig(int boards[],int n,int k,int answer)
{
int painter=1;
int current_board=0;
for(int i=0;i<n;i++)
{
if(current_board+boards[i]>answer)
{
current_board=boards[i];
painter++;
if(painter>k)
{
return false;
}
}
else
{
current_board+=boards[i];
}
}
return true;
}
int binarysearch(int boards[],int n,int k)
{
int s=0;
int total_boards=0;
int e=0;
for(int i=0;i<n;i++)
{
total_boards+=boards[i];
s=max(s,boards[i]);
}
e=total_boards;
int mid=(s+e)/2;
int answer;
while(s<=e)
{
mid=(s+e)/2;
if(isvalidconfig(boards,n,k,mid))
{
answer=mid;
e=mid-1;
}
else
{
s=mid+1;
}
}
return answer;
}
int main() {
int n,k,t;
cin>>n>>k>>t;
int boards[n];
for(int i=0;i<n;i++)
{
cin>>boards[i];
}
cout<<(((binarysearch(boards,n,k))*t)%10000003);
}