#include <iostream>
#define ll long long
using namespace std;
bool condition(ll *a,ll n,ll k,ll ans)
{   
    ll cur_sum=0,painter=0;
    for(ll i=0;i<n;i++)
    {
       if(cur_sum+a[i]<=ans){
            cur_sum+=a[i];
        }
        else
        {
           painter++;
            if(painter>k)
            return false;
            cur_sum=a[i];
        }
    }
    if(cur_sum){
        painter++;
        if(painter>k)
        return false;
    }
    return true;
}
ll bst(ll *a,ll n,ll s,ll e,ll k)
{
    ll ans=0;
    while(s<=e)
    { ll mid=(s+e)/2;
        if(condition(a,n,k,mid))
        {
            ans=mid;
            e=mid-1;
        }
        else
        {
            s=mid+1;
        }
    }
    return ans;
}
int main() {
    ll n,k,t;
    ll total=0,mx=0,s,e;
    cin>>k>>n>>t;
    ll a[n];
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
        total+=a[i];
        mx=max(mx,a[i]);
    }
    s=mx;
    e=total;
    ll ans=bst(a,n,s,e,k)*t;
    cout<<ans%10000003;
}