#include<iostream>
#define Mod 1234567
using namespace std;
int a[100005];
int sum=0,ans=0;
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
{
int x; cin>>x;
sum+=x; sum%=k;
a[sum]++;
}
ans=a[0];
for(int i=0;i<k;i++)
ans+=a[i]*(a[i]-1)>>1;
cout<<ans%Mod<<endl;
return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n,k,c;
unsigned long long sum=0,ans=0,R[100001];

int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&c);
        sum+=c;
        if (sum%k==0) ans++;
        ans=(ans+R[sum%k])%1234567;
        R[sum%k]++;
    }
    cout<<ans<<endl;
    return 0;
}

//前缀和思想以及鸽笼原理的数学思想