Super Bit Strings

You are given an integer n and an array bitStrings of m integers. Each integer represents a binary string of length exactly n: the string is the n-bit binary expansion of that integer, padded on the left with 0s where necessary.

A super bit string of a given bit string is any string obtained by changing any number of its 0s into 1s. A 1 can never be changed back into a 0, and changing nothing at all is allowed, so every bit string is a super bit string of itself.

Count the distinct binary strings of length n that are a super bit string of at least one of the given bit strings. Strings produced from different entries of bitStrings are counted only once.

Function Description

Complete the function countSuperBitStrings in the editor below.

countSuperBitStrings has the following parameters:

int n: the length of every binary string
int bitStrings[m]: the given bit strings, each encoded as an integer in [0, 2^n)

Returns

int: the number of distinct super bit strings that can be formed from the given bit strings.

Constraints

1 <= n <= 20
1 <= m <= 20000, where m is the length of bitStrings
0 <= bitStrings[i] < 2^n
Values in bitStrings may repeat.

Input Format For Custom Testing

The first line contains two space-separated integers, n and m.

The second line contains m space-separated integers, bitStrings[0] through bitStrings[m - 1].

Output Format

Print the single returned value on its own line.

Sample Input 0

5 2
10 26

Sample Output 0

Explanation 0

With n = 5, the value 10 is the string 01010 and the value 26 is the string 11010.

The super bit strings of 01010 are the eight strings 01010, 11010, 01110, 01011, 11110, 11011, 01111, 11111.

Every super bit string of 11010 already appears in that list, because 11010 is itself one of them and turning more 0s into 1s cannot leave the list. So the union has 8 distinct members.

Sample Input 1

3 1
4

Sample Output 1

Explanation 1

With n = 3, the value 4 is the string 100. Its two 0s may each independently stay 0 or become 1, giving 100, 101, 110, 111, that is 4 distinct strings.