#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <list>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;
// 有n个正整数排成一行。你的目的是要从中取出一个或连续的若干个数，使它们的和能够被k整除。
// 例如，有6个正整数，它们依次为1、2、6、3、7、4。若k=3，则你可以取出1、2、6，或者2、6、3、7，也可以仅仅取出一个6或者3使你所取的数之和能被3整除。
// 当然，满足要求的取法不止以上这4种。事实上，一共有7种取法满足要求。
// 给定n和k，以及这n个数。你的任务就是确定，从这n个数中取出其中一个数或者若干连续的数使它们的和能被k整除有多少方法。
// 由于取法可能很多，因此你只需要输出它mod 1234567的值即可。

class Solution_0
{
    // 普通枚举算法
public:
    void solution()
    {
        int size = 0, k = 0;
        cin >> size >> k;
        vector<int> nums(size);
        int count = 0;
        for (int i = 0; i < size; i++)
        {
            cin >> nums[i];
        }
        for (int i = 0; i < size; i++)
        {
            int sum = 0;
            for (int j = i; j < size; j++)
            {
                sum += nums[j];
                if (sum % k == 0)
                {
                    count = (count + 1) % 1234567;
                }
            }
        }
        cout << count << endl;
    }
};
class Solution_1
{
    // 基于动态规划的暴力算法
public:
    void solution()
    {
        int size = 0, k = 0;
        cin >> size >> k;
        vector<int> dp(size, 0);
        int count = 0;
        for (int i = 0; i < size; i++)
        {
            int t = 0;
            cin >> t;
            for (int j = 0; j <= i; j++)
            {
                dp[j] = dp[j] + t;
                if (dp[j] % k == 0)
                    count = (count + 1) % 1234567;
            }
        }
        // vector<vector<int>> dp(size, vector<int>(size, 0));
        // int count = 0;
        // for (int i = 0; i < size; i++)
        // {
        //     cin >> dp[i][i];
        //     if (dp[i][i] % k == 0)
        //     {
        //         count = (count + 1) % 1234567;
        //     }
        //     for (int j = 0; j < i; j++)
        //     {
        //         dp[j][i] = dp[j][i - 1] + dp[i][i];
        //         if (dp[j][i] % k == 0)
        //         {
        //             count = (count + 1) % 1234567;
        //         }
        //     }
        // }
        cout << count << endl;
    }
};
class Solution
{
    // 基于前缀数组和的算法
    // 举个例子，假如输入的size = 6, k = 3, 数组如下
    // nums = {1, 2, 6, 3, 7, 4};
    // 前缀数组A[i]和定义为 A[i] = A[i-1] + nums[i]; 定义A[-1] = 0;
    // 从A中取出两个不同的元素相减可以得到一个片段的和，A[j] - A[i] = nums[i+1] + nums[i+2] + ... + nums[j];
    // nums中的任意一个片段和对应与A中的两个元素或者是A中的一个单独的元素
    // 则A = {1, 3, 9, 12, 19, 24};
    // 考虑A中的元素对k取余数
    // A1 = {1, 0, 0, 0, 1, 0};
    // 当且仅当A1中的两个余数相同时，这两个前缀数组元素相减定义的片段和可以被k整除
    // 理解了以上概念，程序要做的只有两件事
    // 记录前缀数组中拥有相同余数的个数
    // 每次读入一个数，记录sum的余数，将记录中该余数的个数加入到计数器中
    // 此外要注意到的是,nums中的片段有两种定义
public:
    void solution()
    {
        int size = 0, k = 0;
        cin >> size >> k;
        // vector<int> dp(size, 0);
        vector<int> sameRemainder(k + 1, 0);
        int count = 0;
        int sum = 0;
        int t = 0;
        for (int i = 0; i < size; i++)
        {
            cin >> t;
            sum = (sum + t) % k;
            if(sum == 0) 
                count = (count + 1) % 1234567;
            // 存在前缀数组和的余数相同，则两个数组的差的和能被k整除
            count = (count + sameRemainder[sum]) % 1234567;
            sameRemainder[sum]++;
        }
        cout << count << endl;
    }
};

int main(int argc, char const *argv[])
{
    Solution so;
    so.solution();
}