Overview

This problem asks us to count the number of subsets (excluding the empty set) of club activities whose total activity points sum to a multiple of \(K\), modulo \(10^9+7\).

Analysis

Naively enumerating all possible selections (\(2^N\) ways) and checking the sum is far too slow for \(N\le 10^5\).

The key observation here is that to determine whether the sum is a multiple of \(K\), we only need to know the remainder when dividing by \(K\) (i.e., \(0\sim K-1\)), not the sum itself.
In other words, by tracking how many ways there are for each possible remainder of the sum of selected activities so far, we can avoid an enormous search.

For example, when \(K=5\), if we know “how many ways produce a sum with remainder \(2\)” at some point, then when we add a new activity (with remainder \(r\)), the remainder transitions to \((2+r)\bmod 5\).

However, to prevent “using the same activity multiple times within a single update,” the DP update must create a new array from the previous array (in-place updating causes double counting).

Algorithm

We define the DP as follows:

• \(dp[j]\): the number of ways to select some activities seen so far such that the total activity points modulo \(K\) equals \(j\) (\(\bmod\ 10^9+7\))

The initial state contains only the empty set, so: - \(dp[0]=1\), and all others are \(0\)

For each activity’s points \(a\), let \(r=a\bmod K\).
If we “don’t select” this activity, the remainder stays the same; if we “select” it, the remainder changes to \((j+r)\bmod K\).

Therefore, the transitions are: - Don’t select: \(newdp[j] \mathrel{+}= dp[j]\) - Select: \(newdp[(j+r)\bmod K] \mathrel{+}= dp[j]\)

performed for all \(j\).

Finally, we want the count for “sum is a multiple of \(K\),” meaning remainder \(0\), but since the problem forbids the empty set: - Answer \(= dp[0]-1\) (subtract the empty set)

Concrete Example

When \(K=3\), \(A=[1,2]\): - Initial: \(dp=[1,0,0]\) (empty set only) - Process \(1\) (\(r=1\))
- Selecting from the empty set adds 1 way with remainder \(1\)
→ \(dp=[1,1,0]\) - Process \(2\) (\(r=2\))
- From remainder \(0\) (empty), selecting → remainder \(2\) increases
- From remainder \(1\) ({1}), selecting → remainder \((1+2)\bmod 3=0\) increases ({1,2})
→ \(dp=[2,1,1]\)

Here, remainder \(0\) has 2 ways (empty set and {1,2}), so excluding the empty set, the answer is \(2-1=1\).

Complexity

• Time complexity: \(O(NK)\) (for each activity, update remainders \(0\sim K-1\))
• Space complexity: \(O(K)\) (only store counts per remainder)

Implementation Notes

• Include the empty set as \(dp[0]=1\), and subtract \(1\) at the end to exclude it.

• To avoid using a single activity multiple times within the same update, copy the array before transitioning, e.g., newdp = dp[:] (in-place updating is not allowed).

• When \(K=1\), every non-empty subset satisfies the condition, so the answer is \(2^N-1\), which can be computed efficiently (the code also uses an early return for this case).

• Take the modulus \(10^9+7\) at each transition to prevent overflow and excessively large numbers.

  Source Code

import sys

MOD = 10**9 + 7

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    A = data[2:]

    if K == 1:
        print((pow(2, N, MOD) - 1) % MOD)
        return

    dp = [0] * K
    dp[0] = 1  # empty subset

    for a in A:
        r = a % K
        newdp = dp[:]  # not taking this club
        for j in range(K):
            v = dp[j]
            idx = j + r
            if idx >= K:
                idx -= K
            x = newdp[idx] + v
            if x >= MOD:
                x -= MOD
            newdp[idx] = x
        dp = newdp

    ans = dp[0] - 1  # exclude empty subset
    if ans < 0:
        ans += MOD
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.