1class Solution {
2    // Maximum size for factorial precomputation and bit-state dimension.
3    // N = 31 covers indices 0..30 (m can be up to 30).
4    static final int N = 31;
5
6    // Modulo value for all arithmetic to prevent overflow.
7    static final long MOD = 1_000_000_007L;
8
9    // factorial[i] = i! % MOD
10    private static final long[] factorial = new long[N];
11
12    // inverseFactorial[i] = modular multiplicative inverse of i! under MOD
13    private static final long[] inverseFactorial = new long[N];
14
15    // 4-dimensional memoization cache:
16    // memo[index][remaining][targetSetBits][carry]
17    private Long[][][][] memo;
18
19    // Static initializer: precompute factorials and their modular inverses.
20    static {
21        factorial[0] = 1;
22        inverseFactorial[0] = 1;
23        for (int i = 1; i < N; ++i) {
24            factorial[i] = factorial[i - 1] * i % MOD;
25            // Fermat's little theorem: inverse of x is x^(MOD-2) under prime MOD.
26            inverseFactorial[i] = qpow(factorial[i], MOD - 2);
27        }
28    }
29
30    /**
31     * Fast exponentiation: computes (base^exponent) % MOD.
32     *
33     * @param base     the base value
34     * @param exponent the exponent value
35     * @return base raised to exponent, taken modulo MOD
36     */
37    public static long qpow(long base, long exponent) {
38        long result = 1;
39        while (exponent != 0) {
40            // If the lowest bit is set, multiply current base into the result.
41            if ((exponent & 1) == 1) {
42                result = result * base % MOD;
43            }
44            // Square the base and shift to the next bit.
45            base = base * base % MOD;
46            exponent >>= 1;
47        }
48        return result;
49    }
50
51    /**
52     * Computes the binomial coefficient C(total, choose) modulo MOD,
53     * using precomputed factorials and inverse factorials.
54     *
55     * @param total  the total number of items (n in "n choose r")
56     * @param choose the number of items chosen (r in "n choose r")
57     * @return C(total, choose) % MOD
58     */
59    public static long comb(int total, int choose) {
60        return factorial[total]
61                * inverseFactorial[choose] % MOD
62                * inverseFactorial[total - choose] % MOD;
63    }
64
65    /**
66     * Counts the number of "magical" ways to distribute m selections across
67     * the elements of nums such that the resulting popcount condition equals k.
68     *
69     * @param m    the total number of selections to distribute
70     * @param k    the required number of set bits in the accumulated value
71     * @param nums the array of base values
72     * @return the count of valid arrangements modulo MOD
73     */
74    public int magicalSum(int m, int k, int[] nums) {
75        int n = nums.length;
76        // Dimensions: index (0..n), remaining (0..m), targetBits (0..k), carry (0..N-1).
77        memo = new Long[n + 1][m + 1][k + 1][N];
78        long ans = dfs(0, m, k, 0, nums);
79        return (int) ans;
80    }
81
82    /**
83     * Recursive DFS with memoization.
84     *
85     * @param index            current index into nums being processed
86     * @param remaining        number of selections still to distribute
87     * @param targetBits       remaining set-bit budget still needed
88     * @param carry            carry value propagated from lower bit positions
89     * @param nums             the array of base values
90     * @return the number of valid completions from this state, modulo MOD
91     */
92    private long dfs(int index, int remaining, int targetBits, int carry, int[] nums) {
93        // Prune: negative bit budget, or run out of array but still owe selections.
94        if (targetBits < 0 || (index == nums.length && remaining > 0)) {
95            return 0;
96        }
97
98        // Base case: all elements processed.
99        if (index == nums.length) {
100            // The leftover carry's set bits must exactly consume the remaining budget.
101            while (carry > 0) {
102                targetBits -= (carry & 1);
103                carry >>= 1;
104            }
105            return targetBits == 0 ? 1 : 0;
106        }
107
108        // Return cached result if this state was already computed.
109        if (memo[index][remaining][targetBits][carry] != null) {
110            return memo[index][remaining][targetBits][carry];
111        }
112
113        long result = 0;
114        // Try assigning t selections to the current element (0..remaining).
115        for (int t = 0; t <= remaining; t++) {
116            // Combine current selections with incoming carry.
117            int newCarry = t + carry;
118            // Consume one bit of budget if the current bit position is set.
119            int newTargetBits = targetBits - (newCarry & 1);
120            // Contribution factor: nums[index]^t.
121            long power = qpow(nums[index], t);
122            // Multiply by the number of ways to choose which t of the remaining are used,
123            // then recurse with the carry shifted to the next bit position.
124            long contribution = comb(remaining, t)
125                    * power % MOD
126                    * dfs(index + 1, remaining - t, newTargetBits, newCarry >> 1, nums) % MOD;
127            result = (result + contribution) % MOD;
128        }
129
130        // Cache and return.
131        return memo[index][remaining][targetBits][carry] = result;
132    }
133}
134

1class Solution {
2public:
3    // Public entry point. Method name kept as required.
4    int magicalSum(int m, int k, vector<int>& nums) {
5        this->nums = nums;
6        int n = static_cast<int>(nums.size());
7
8        // Precompute factorials and their modular inverses once.
9        ensureCombInit();
10
11        // dp[i][j][bitsLeft][state]:
12        //   i        -> index into nums currently being processed
13        //   j        -> remaining count of elements still to distribute
14        //   bitsLeft -> remaining number of set bits (popcount budget) we must place
15        //   state    -> accumulated carry coming from lower bit positions
16        // Initialized to -1 to mark "not computed yet".
17        dp.assign(
18            n + 1,
19            vector<vector<vector<long long>>>(
20                m + 1,
21                vector<vector<long long>>(
22                    k + 1,
23                    vector<long long>(kMaxN, -1))));
24
25        return static_cast<int>(dfs(0, m, k, 0));
26    }
27
28private:
29    // Maximum dimension for factorial tables and state size.
30    static const int kMaxN = 31;
31    static const long long kMod = 1'000'000'007;
32
33    // factorial[i] = i! mod kMod
34    // invFactorial[i] = (i!)^{-1} mod kMod
35    long long factorial[kMaxN];
36    long long invFactorial[kMaxN];
37    bool combReady = false;
38
39    vector<int> nums;
40
41    // Memoization table (see dimensions described in magicalSum).
42    vector<vector<vector<vector<long long>>>> dp;
43
44    // Fast modular exponentiation: returns (base^exp) mod kMod.
45    long long qpow(long long base, long long exp) {
46        long long result = 1;
47        base %= kMod;
48        while (exp) {
49            if (exp & 1) {
50                result = result * base % kMod;
51            }
52            base = base * base % kMod;
53            exp >>= 1;
54        }
55        return result;
56    }
57
58    // Lazily precompute factorials and modular inverse factorials.
59    void ensureCombInit() {
60        if (combReady) {
61            return;
62        }
63        factorial[0] = invFactorial[0] = 1;
64        for (int i = 1; i < kMaxN; ++i) {
65            factorial[i] = factorial[i - 1] * i % kMod;
66            // Fermat's little theorem: inverse = a^(MOD-2) mod MOD.
67            invFactorial[i] = qpow(factorial[i], kMod - 2);
68        }
69        combReady = true;
70    }
71
72    // Binomial coefficient C(total, choose) mod kMod.
73    long long comb(int total, int choose) {
74        return factorial[total] * invFactorial[choose] % kMod
75               * invFactorial[total - choose] % kMod;
76    }
77
78    // Recursive DP with memoization.
79    //   index    -> current position in nums
80    //   remain   -> remaining elements to distribute among nums[index..]
81    //   bitsLeft -> remaining popcount budget to satisfy
82    //   state    -> carry accumulated from lower bit positions
83    long long dfs(int index, int remain, int bitsLeft, int state) {
84        // Prune: overspent the popcount budget, or finished nums but still
85        // have leftover elements to place.
86        if (bitsLeft < 0 || (index == static_cast<int>(nums.size()) && remain > 0)) {
87            return 0;
88        }
89
90        // Reached the end with all elements placed: flush remaining carry bits
91        // into the popcount budget and check it lands exactly on zero.
92        if (index == static_cast<int>(nums.size())) {
93            while (state > 0) {
94                bitsLeft -= (state & 1);
95                state >>= 1;
96            }
97            return bitsLeft == 0 ? 1 : 0;
98        }
99
100        long long& result = dp[index][remain][bitsLeft][state];
101        if (result != -1) {
102            return result;
103        }
104
105        result = 0;
106        // Try assigning t copies to the current nums[index].
107        for (int t = 0; t <= remain; ++t) {
108            // Add the incoming carry to the count chosen at this position.
109            int combined = t + state;
110            // This bit contributes (combined & 1) to the popcount budget.
111            int nextBits = bitsLeft - (combined & 1);
112            // Contribution of choosing nums[index] exactly t times.
113            long long powVal = qpow(nums[index], t);
114            long long tmp = comb(remain, t) * powVal % kMod
115                            * dfs(index + 1, remain - t, nextBits, combined >> 1) % kMod;
116            result = (result + tmp) % kMod;
117        }
118        return result;
119    }
120};
121

1// Modulus used throughout the computation.
2const kMod = 1_000_000_007n;
3
4// Maximum dimension for factorial tables and the state (carry) size.
5const kMaxN = 31;
6
7// factorial[i]    = i! mod kMod
8// invFactorial[i] = (i!)^{-1} mod kMod
9const factorial: bigint[] = new Array(kMaxN).fill(0n);
10const invFactorial: bigint[] = new Array(kMaxN).fill(0n);
11
12// Flag to ensure factorial tables are computed only once.
13let combReady = false;
14
15// Shared input array (assigned at the start of magicalSum).
16let nums: number[] = [];
17
18// Memoization table:
19//   dp[index][remain][bitsLeft][state]
20// Initialized lazily inside magicalSum. A value of -1n means "not computed yet".
21let dp: bigint[][][][] = [];
22
23/**
24 * Fast modular exponentiation: returns (base^exp) mod kMod.
25 */
26function qpow(base: bigint, exp: bigint): bigint {
27  let result = 1n;
28  base %= kMod;
29  while (exp > 0n) {
30    if (exp & 1n) {
31      result = (result * base) % kMod;
32    }
33    base = (base * base) % kMod;
34    exp >>= 1n;
35  }
36  return result;
37}
38
39/**
40 * Lazily precompute factorials and modular inverse factorials.
41 */
42function ensureCombInit(): void {
43  if (combReady) {
44    return;
45  }
46  factorial[0] = 1n;
47  invFactorial[0] = 1n;
48  for (let i = 1; i < kMaxN; ++i) {
49    factorial[i] = (factorial[i - 1] * BigInt(i)) % kMod;
50    // Fermat's little theorem: inverse = a^(MOD-2) mod MOD.
51    invFactorial[i] = qpow(factorial[i], kMod - 2n);
52  }
53  combReady = true;
54}
55
56/**
57 * Binomial coefficient C(total, choose) mod kMod.
58 */
59function comb(total: number, choose: number): bigint {
60  return (
61    ((factorial[total] * invFactorial[choose]) % kMod) *
62    invFactorial[total - choose]
63  ) % kMod;
64}
65
66/**
67 * Recursive DP with memoization.
68 *   index    -> current position in nums
69 *   remain   -> remaining elements to distribute among nums[index..]
70 *   bitsLeft -> remaining popcount budget to satisfy
71 *   state    -> carry accumulated from lower bit positions
72 */
73function dfs(index: number, remain: number, bitsLeft: number, state: number): bigint {
74  // Prune: overspent the popcount budget, or finished nums but still
75  // have leftover elements to place.
76  if (bitsLeft < 0 || (index === nums.length && remain > 0)) {
77    return 0n;
78  }
79
80  // Reached the end with all elements placed: flush remaining carry bits
81  // into the popcount budget and check it lands exactly on zero.
82  if (index === nums.length) {
83    while (state > 0) {
84      bitsLeft -= state & 1;
85      state >>= 1;
86    }
87    return bitsLeft === 0 ? 1n : 0n;
88  }
89
90  // Return cached value if present.
91  const cached = dp[index][remain][bitsLeft][state];
92  if (cached !== -1n) {
93    return cached;
94  }
95
96  let result = 0n;
97  // Try assigning t copies to the current nums[index].
98  for (let t = 0; t <= remain; ++t) {
99    // Add the incoming carry to the count chosen at this position.
100    const combined = t + state;
101    // This bit contributes (combined & 1) to the popcount budget.
102    const nextBits = bitsLeft - (combined & 1);
103    // Contribution of choosing nums[index] exactly t times.
104    const powVal = qpow(BigInt(nums[index]), BigInt(t));
105    const tmp =
106      (((comb(remain, t) * powVal) % kMod) *
107        dfs(index + 1, remain - t, nextBits, combined >> 1)) %
108      kMod;
109    result = (result + tmp) % kMod;
110  }
111
112  dp[index][remain][bitsLeft][state] = result;
113  return result;
114}
115
116/**
117 * Public entry point. Method name kept as required.
118 */
119function magicalSum(m: number, k: number, nums_: number[]): number {
120  nums = nums_;
121  const n = nums.length;
122
123  // Precompute factorials and their modular inverses once.
124  ensureCombInit();
125
126  // Initialize dp[i][j][bitsLeft][state] to -1n ("not computed yet"):
127  //   i        -> index into nums currently being processed
128  //   j        -> remaining count of elements still to distribute
129  //   bitsLeft -> remaining number of set bits (popcount budget) we must place
130  //   state    -> accumulated carry coming from lower bit positions
131  dp = Array.from({ length: n + 1 }, () =>
132    Array.from({ length: m + 1 }, () =>
133      Array.from({ length: k + 1 }, () =>
134        new Array<bigint>(kMaxN).fill(-1n),
135      ),
136    ),
137  );
138
139  return Number(dfs(0, m, k, 0));
140}
141