1328. Count Subsets with Given AND Value

Given an array of non-negative integers and a target k, count how many non-empty subsets have a bitwise AND exactly equal to k. The empty subset is excluded because its AND is undefined.

Input: A JSON object {"nums": [<non-negative integers>], "k": <target>}.

Output: Return the number of non-empty subsets whose AND equals k.

Examples

Input: {"nums":[7,3,5],"k":1}
Output: 2
Explanation: Subsets {3,5} and {7,3,5} AND to 1 -> 2.

Input: {"nums":[4,4],"k":4}
Output: 3
Explanation: Subsets {4}, {4} and {4,4} all AND to 4 -> 3.

Constraints

• 1 <= len(nums) <= 20
• 0 <= nums[i], k < 1024

Asked by