A mission needs m distinct skills, numbered 0 to m-1. Each of n candidates has a skill set encoded as a bitmask over these m skills (bit s set means the candidate has skill s).
A team is any subset of candidates. A team covers the mission if the bitwise OR of its members' masks has all m bits set (every skill is possessed by at least one member). The empty team covers nothing.
Count how many teams cover the mission.
Input format
Line 1: two space-separated integers n and m.
Line 2: n space-separated integers, each a skill mask in the range 0 .. 2^m - 1.
Output format
A single integer: the number of teams whose combined skills cover all m skills.
Constraints
- 1 <= n <= 18
- 1 <= m <= 12
- 0 <= each mask <= 2^m - 1