Find Sum of Array Product of Magical Sequences
You are given two integers, m and k, and an integer array nums.
A sequence of integers seq is called magical if:
seqhas a size ofm.0 <= seq[i] < nums.length.- The binary representation of
2^seq[0] + 2^seq[1] + ... + 2^seq[m - 1]haskset bits.
The array product of this sequence is defined as prod(seq) = (nums[seq[0]] * nums[seq[1]] * ... * nums[seq[m - 1]]).
Return the sum of the array products for all valid magical sequences.
Since the answer may be large, return it modulo 10^9 + 7.
A set bit refers to a bit in the binary representation of a number that has a value of 1.
Example 1
Input
m = 5, k = 5, nums = [1,10,100,10000,1000000]Output
991600007All permutations of [0, 1, 2, 3, 4] are magical sequences, each with an array product of 10^13.
Example 2
Input
m = 2, k = 2, nums = [5,4,3,2,1]Output
170The magical sequences are all ordered pairs of distinct indices from 0 to 4, and their array products sum to 170.
Constraints
- 1 <= k <= m <= 30
- 1 <= nums.length <= 50
- 1 <= nums[i] <= 10^8