#include<bits/stdc++.h>
using namespace std;
#define ll long long int
bool check(ll k,ll a[],ll n,ll time)
{
ll count=1;
ll sum=0;
for(int i=0;i<n;i++)
{
if(a[i]>time)
{
return false;
}
if(sum+a[i]<=time)
{
sum+=a[i];
}
else
{
count++;
sum=a[i];
if(count>k)
return false;
}
}
return true;
}
int main()
{
ll k,n,t;
cin >> k >> n;
cin >> t;
ll a[n];
for(ll i=0;i<n;i++)
cin >> a[i];
ll l;
ll max=a[0];
ll sum=0;
for(ll i=0;i<n;i++)
{
sum+=a[i];
if(a[i] > max)
max=a[i];
}
l=max;
ll r=sum;
ll ans=0;
while(l<=r)
{
ll mid=(l+r)/2;
if(check(k,a,n,mid))
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
cout<<((ans%10000003)*t)%10000003<<endl;
}
