ABC 378

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vll A(N);
    rep(i, N) cin >> A[i];

    vll cm(N + 1);
    rep(i, N) {
        cm[i + 1] = cm[i] + A[i];
        cm[i + 1] %= M;
    }

    fenwick_tree<ll> freq(M), cmcm(N + 1);
    rep(i, N) cmcm.add(i + 1, cm[i + 1]);

    ll ans = 0;
    rep2(i, 1, N + 1) {
        ans += i * cm[i];
        ans -= cmcm.sum(0, i);
        freq.add(cm[i], 1);
        ans += M * freq.sum(cm[i] + 1, M);
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;

    vll A(N);
    rep(i, N) cin >> A[i];
    vll cm(N + 1);
    rep(i, N) cm[i + 1] = (cm[i] + A[i]) % M;

    fenwick_tree<ll> fw(M);

    ll ans = 0;
    ll sum = 0;
    rep(r, N + 1) {
        ans += cm[r] * r - sum + fw.sum(cm[r] + 1, M) * M;
        sum += cm[r];
        fw.add(cm[r], 1);
    }
    cout << ans << endl;
}