Problem Statement

Subsequences With Exactly K Set Bits You are given an array a of n non-negative integers and an integer k . Count the number of non-empty subsequences of a for which the bitwise AND of the chosen elements has exactly k set bits in its binary representation. A subsequence of an array a is a sequence that can be obtained from a by removing some (possibly zero) elements without changing the order of the remaining ones. For example, [1, 2, 3] , [3] and [1, 3] are subsequences of [1, 2, 3] , but [3, 2] and [4, 5, 6] are not. Two subsequences are considered different if the set of chosen positions is different, even when the chosen values are identical. The answer may be large, so return it modulo 10^9 + 7 . Function countSubsequences(a: int[], k: int) -> int Complete the function countSubsequences in the editor. countSubsequences has the following parameters: int a[n] : the array int k : the required number of set bits Returns int : the number of non-empty subsequences whose bitwise AND