Overview

We select exactly \(K\) people from \(N \le 30\) people, and count the number of ways such that the sum of ability values is a multiple of \(M\) (\(\bmod M = 0\)). Since \(N\) is relatively small, we use Meet-in-the-Middle to efficiently enumerate and count.

Approach

Key Insight

The essential observation is that the condition “the sum of the selected set is a multiple of \(M\)” only requires looking at the remainder (\(\bmod M\)) of the sum.

Also, since \(N \le 30\), the total number of combinations can be as large as \({30 \choose 15} \approx 1.55 \times 10^8\), so naively “enumerating all combinations of \(K\) people and computing the sum” is too slow (especially prone to TLE in Python).

How to Solve It (Meet-in-the-Middle)

Split the array into two halves:

• Left: \(n_1 = \lfloor N/2 \rfloor\) people
• Right: \(n_2 = N - n_1\) people

For each half, enumerate all subsets. The number of subsets is at most \(2^{15} = 32768\), which is very manageable.

Here, let: - \(r_L\) be the remainder of the sum when selecting \(s\) people from the left - \(r_R\) be the remainder of the sum when selecting \(t\) people from the right

To select \(K\) people total, we need \(s+t=K\), and the condition becomes: [ (r_L + r_R) \bmod M = 0 ] In other words: [ r_R \equiv -r_L \pmod M ] This reduces to a “matching” problem where we count the number of right-side remainders satisfying this condition.

Concrete Example (Illustration)

For example, if \(M=7\) and a subset of \(s=2\) people selected from the left has sum remainder \(r_L=3\), then the subset of \(t=K-2\) people selected from the right must have remainder \((-3)\bmod 7 = 4\). If the left side has \(c\) subsets with remainder \(3\) and the right side has \(d\) subsets with remainder \(4\), then this combination contributes \(c \times d\) ways.

Algorithm

1. Split array \(A\) into two halves (left, right).
2. For each half, enumerate all subsets and compute:
   • The number of elements in the subset (how many people are selected)
   • The remainder of the subset sum (\(\bmod M\))

Count these in the following form: [ \text{cnt}[k][r] = \text{“number of subsets selecting }k\text{ people from this half with sum}\bmod M=r\text{”} ] In the implementation, this is stored as dicts[k][r] (dictionary), because \(M\) can be up to \(10^9\), making it impossible to have an array of size \(0..M-1\). 3. Iterate over \(s\), the number of people selected from the left: - The valid range of \(s\), using the right-side count \(n_2\), is: [ \max(0, K-n_2) \le s \le \min(n_1, K) ] - Set \(t = K-s\) and match left dL[s] with right dR[t]. 4. For each left remainder \(r\), the required right remainder is \((-r)\bmod M\), so accumulate: [ \text{ans} += \text{dL}[s][r] \times \text{dR}[t][(-r)\bmod M] ] (managing the result modulo \(10^9+7\)). 5. Output the final answer.

Optimization in build

In build, for every mask (\(0..2^n-1\)): - lsb = mask & -mask (lowest set bit) - prev = mask ^ lsb (the set with that bit removed)

Then compute: [ \text{sums}[mask] = (\text{sums}[prev] + \text{added element}) \bmod M ] [ \text{bits}[mask] = \text{bits}[prev] + 1 ] This efficiently computes the “sum mod M” and “number of people” for each subset.

Complexity

• Time complexity:
  Subset enumeration for each half is \(O(2^{n_1} + 2^{n_2})\), and the matching step is roughly proportional to the number of distinct remainders that appear, so it is about the same order.
  Overall: [ O(2^{N/2}) ] (There are constant factors, but this is well within limits for \(N \le 30\).)
• Space complexity:
  Since we store information for all subsets of both halves: [ O(2^{N/2}) ] (for the sums, bits arrays and the per-size dictionaries).

Implementation Notes

• Since \(M\) can be very large, we cannot create an array of size \(0..M-1\). It is crucial to use dictionaries (defaultdict(int)) to count only the remainders that actually appear.

• Always narrow the range of \(s\) satisfying \(s+t=K\) (s_min, s_max). Avoiding unnecessary cases reduces waste.

• Since the answer is a combinatorial count and can be enormous, take the remainder modulo \(10^9+7\) at every addition and multiplication.

• During the matching step, iterating over the smaller dictionary (the small, large optimization in the code) improves speed.

  Source Code

import sys
from collections import defaultdict

MOD = 10**9 + 7

def build(arr, M):
    n = len(arr)
    size = 1 << n
    sums = [0] * size
    bits = [0] * size

    for mask in range(1, size):
        lsb = mask & -mask
        i = lsb.bit_length() - 1
        prev = mask ^ lsb
        sums[mask] = (sums[prev] + arr[i]) % M
        bits[mask] = bits[prev] + 1

    dicts = [defaultdict(int) for _ in range(n + 1)]
    for mask in range(size):
        dicts[bits[mask]][sums[mask]] += 1
    return dicts

def main():
    input = sys.stdin.readline
    N, K, M = map(int, input().split())
    A = list(map(int, input().split()))

    n1 = N // 2
    left = A[:n1]
    right = A[n1:]

    dL = build(left, M)
    dR = build(right, M)

    ans = 0
    n2 = N - n1

    s_min = max(0, K - n2)
    s_max = min(n1, K)

    for s in range(s_min, s_max + 1):
        t = K - s
        d1 = dL[s]
        d2 = dR[t]

        if len(d1) <= len(d2):
            small, large = d1, d2
        else:
            small, large = d2, d1

        for r, c in small.items():
            ans = (ans + (c % MOD) * (large.get((-r) % M, 0) % MOD)) % MOD

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.